GablrielGraph拓扑控制图的python图像实现

问题:

拓扑控制（topology control）
是一种协调节点间各自传输范围的技术，用以构建具有某些期望的全局特性（如连通性）的网络拓扑结构，同时减少节点的能耗或增加网络的传输能力。
选取一种拓扑控制算法(如 RNG、GG、DG、YG、MST、DRNG、 DLMST、DLSS，TopDisc 等)，编程实现该算法并用图形显示效果。要求有执行算法前后拓扑对比图、链路数量统计对比。节点数目最少 50 个，随机分布，其他如通信半径、部署区域大小等自行选取。考虑到连通性问题，要求应用拓扑控制的初始网络为全连通网络（即每个节点与其他任意节点至少存在一条链路，随机生成节点位置时可多试几次或增加节点密度）

插入图片

拓扑算法的选择与原理

1. UDG(Unit Disk Graph)

定义：假定网络中N个节点构成了二维平面中的节点V所有节点都以最大功率工作时所产生的拓扑成为UDG
思路：每个节点遍历其余结点坐标，计算彼此距离(功率)，属于范围内的节点连接成边缘，将边缘加入列表

$u,v\in V dis(u,v)\leq D_{max}(u)$

2. GG(Gabriel Graph)

定义：任意两个节点u和v，以边u、v为直径的圆内没有其他节点
思路：每个节点遍历其余结点坐标，计算彼此距离(功率)，判断是否属于范围内，且彼此连接圆内只有目标节点一个，成功便将边缘加入列表

$w,u,v\in V dis(u,v)\leq D_{max}(u) \quad \forall w\ \neq u,v: d^2(u,v)<[d^2(u,w)+d^2(v,w)]$

程序框架

config.py：定义了随机初始化节点函数
util.py：定义了针对单个节点，利用udg或gg思想，遍历其余所有节点返回生成的边缘列表有关方法
gg.py：gg图演示程序

源码

gg.py

#初始化节点
nodes = node_init(_num=50,_rad_max=300)
# edge1=edge_init(0,nodes[0],nodes[1])#初始化一条边
#计算所有边（gg）
edges=[]
for i in range(len(nodes)):
    edges.append(trav2gg(nodes[i],nodes))
#将边缘对象转化为画图所需的边
for i in edges:
    for j in i:
        edgelist.append((j.node1_id,j.node2_id))
#画点
g_gg = nx.Graph()
g_gg.add_nodes_from([i for i in range(len(nodes))])
pos = {i:(nodes[i].x,nodes[i].y) for i in range(len(nodes))}
nx.draw_networkx_nodes(g_gg,pos=pos,
    node_color = 'black',node_size = 20)
nx.draw_networkx_edges(g_gg,pos = pos,edgelist=edgelist,
    edge_color='r',width =0.8)
plt.show()

config.py

#生成随机位置
def position_random(_wid, _hei):
    x = random.randint(0, _wid)
    y = random.randint(0, _hei)
    return [x, y]
#生成指定数量节点
def node_init(_a=[wid, hei], _rad_max=rad_max, _num=node_num):
    nodes = []
    positions = []
    for i in range(_num):
        pos = position_random(_a[0], _a[1])
        if pos not in positions:
            positions.append(pos)
            nodes.append(e.Node(i, pos[0], pos[1], _rad_max))
    return nodes

util.py

def trav2gg(_node, _node_list):
    edge_list = []#存放遍历后该节点的边界
    node_list=[]#存放遍历后的该节点的邻居节点
    #UDG算法计算该节点的全部邻居节点以及边缘
    for i, value in enumerate(_node_list):
        _edge = edge_init('edge', _node, value)
        if _edge.length < _node.r and value.id != _node.id:
            edge_list.append(_edge)
            node_list.append(value)
    # GG算法计算该在UDG子集中的边界
    edge_list_out=[]#存放gg算法该节点的边界
    for i in edge_list:
        # 判断是否只有目标节点一个，在其与源节点两点所成的圆上
        if is_onemin(_node,_node_list[i.node2_id],node_list):
            edge_list_out.append(i)
    return edge_list_out