基于剩余能量感知的分布式容错拓扑控制方法

摘要

本发明公开了一种基于剩余能量感知的分布式容错拓扑控制方法，主要解决现有技术中不能同时保证节点间剩余能量平衡和网络拓扑容错能力的问题。其实现过程为：网络中的每个节点广播自己的HELLO包并接收初始邻节点的HELLO包，建立局部拓扑子图；基于局部拓扑子图，先根据链路代价权重，构建最短路径树，再按距离权重从小到大遍历所有有向边，构建局部k连通生成子图；根据局部k连通生成子图中的一跳邻节点调整发射功率，并连接此发射功率范围内的非逻辑邻节点；最后由网络中的所有节点以及节点与其逻辑邻节点间的链路构成全网拓扑；上述过程按拓扑更新周期T重复执行。本发明具有延长网络生存期，增强网络容错能力的优点，可用于无线自组织网络。

主权项

一种基于剩余能量感知的分布式容错拓扑控制方法，包括如下步骤：(1)网络中每个节点u发送自己的HELLO包，并接收初始邻节点发送的HELLO包,该HELLO包中包括节点的ID序列号、剩余能量信息以及位置信息；(2)网络中每个节点u构建自己的局部拓扑子图G_u：(2a)网络中的每个节点u根据接收到的初始邻节点的HELLO包信息，确定自己与初始邻节点的连接关系，以及这些初始邻节点之间的连接关系，建立局部拓扑子图G_u；(2b)根据局部拓扑子图，每个节点u计算局部拓扑子图中任意两个有连接关系的节点x,y之间的链路代价权重及距离权重(3)网络中每个节点u构建局部k连通生成子图S_u＝(V(S_u),E(S_u))：(3a)网络中的每个节点u将局部k连通生成子图S_u的节点集合V(S_u)初始化成局部拓扑子图中所有节点，将局部k连通生成子图S_u的边集合E(S_u)初始化成空集；(3b)基于局部拓扑子图，每个节点u根据链路代价权重构建以u为根，遍及局部拓扑子图中所有节点的最短路径树T_u＝(V(T_u),E(T_u))，其中V(T_u)＝V(G_u)为局部拓扑子图中所有节点，E(T_u)为构成最短路径树的所有有向边；(3c)把最短路径树T_u中的有向边E(T_u)全部添加到局部k连通生成子图S_u中，即表示赋值，∪表示两个集合的并；(3d)对局部拓扑子图中的有向边按距离权重大小进行排序，获得有序的边序列E′(G_u)；(3e)遍历E′(G_u)中的每条有向边(x,y)，若判断节点x,y在S_u中是否达到k连通：若S_u中x,y没有达到k连通，则把(x,y)添加到E(S_u)中，即(x,y)∈E(S_u)，然后开始遍历下一条边，直至遍历完E′(G_u)中的全部有向边；若S_u中x,y已达到k连通，则直接遍历下一条边，直至遍历完E′(G_u)中的全部有向边；(3f)每个节点u将局部k连通生成子图S_u上的一跳邻节点v作为逻辑邻节点，并构成逻辑邻节点集：LN_u＝{v∈V(S_u)|(u,v)∈E(S_u)}；(4)网络中每个节点u确定自己的发射功率，即将发射功率调整为能够覆盖到局部k连通生成子图S_u中最远的逻辑邻节点所需要的最小功率：(5)每个节点u检查在其发射功率所对应的传输半径范围内是否存在非逻辑邻节点z：若存在非逻辑邻节点z，则把节点u到该节点z的链路添加到局部k连通生成子图S_u中；若不存在非逻辑邻节点z，则保持原局部k连通生成子图S_u不变；(6)将网络中的所有节点以及每个节点与自己的逻辑邻节点间的链路组合起来，构成最终的全网拓扑，即G＝(V(G),E(G))，其中V(G)为网络中所有节点，E(G)＝{(u,v)|u∈V(G),v∈LN_u}；(7)在经过一个拓扑更新周期T的时间后，开始重新执行上述步骤1～步骤6。