无线多跳网络的局部拓扑算法

孙智博

（中南大学信息科学与工程学院 湖南长沙 410000）

无线多跳网络的局部拓扑算法

孙智博

（中南大学信息科学与工程学院 湖南长沙 410000）

无线多跳网络的拓扑结构对网络性能有较大的影响。在许多情况下，无线多跳网络中的节点往往是靠电池供电。当节点的电池能量耗尽时，节点便不能再继续工作。拓扑控制的目标是实现稀疏性，减少能量消耗和无线接口，控制传输功率，并且延长网络寿命。

无线多跳网络；拓扑算法

中提出了一种局部的节能拓扑控制算法X-LMST，可以通过在维持节点中的能量消耗平衡，有效地实现延长网络的生命周期。算法复杂度是O（mlogn），m代表的是链路数量，n代表的是距离一个节点的“单跳”的相邻节点的数量。

文献中做出以下假设：①网络中的每个节点能够自适应地调整其发射功率；②假设每个节点都配备了全方位天线；③干扰电平独立于网络流量，并且所有节点的干扰电平相同；④所有节点都知道其位置信息（可以通过某些定位技术或设备，例如GPS接收器），并且每个节点保持所有单跳相邻节点的位置信息（这种位置信息可利用当网络最初部署时，邻域节点之间交换hello消息的方式获得，如果节点移动，可以定期交换等hello消息）；⑤假设MAC层是理想的，这可以保证数据包总是可以不丢失。

建立图模型 G（V，E），V（G）代表节顶点集，E（G）代表边集。（u，v）∈E（G）表示 u，v之间直接相连。如果的、d（u，v）≤R，那么 u，v之间存在链路（d（u，v）代表u，v两点之间的几何距离，而R代表节点在网络中的最大均匀传输范围）。

用euv代表节点u成功传送信息单元到节点v所需的最小功率，在d（u，v）≤R 的前提下，euv=d（u，v）α+c，α 和 c是常数在特定的无线系统和传播环境中（通常2≤α≤4）。c代表着由信号处理和成功接收信息所需的最小能量所造成的开销。当d（u，v）＞R，euv接近∞。对于给定的连接节点的路径p，发送一个信息单元的整体功耗是链路中所有节点发射功率的总和。，用N（u）代表节点u的单跳相邻节点集合，那么N（u）={v|v∈V（G），（u，v）∈E（G）}+{u}。让 NE（u）表示 N（u）的两个节点之间的边的集合，那么NE（u）={（x，y）|（x，y）∈E（G）∧x，y∈N（u）}。该算法主要实现两个目标：①减少网络节点的传输功率；②延长网络的生存时间。

X-LMST中的关键问题是如何确定网络中的链路的能量临界值。该文献定义了一个新的度量值。为了判定是否是能量关键链路，需要对链路的两个端点节点的能量状态进行检查。通常认为，如果它们其中一个具有极低的能量，不管另一个节点剩余能量多么高，应考虑该链路为能源关键链路。

想要描述每个节点影响一个在其单跳邻域的链路是否是能量关键链路的程度，可以引入Lx表示每一个节点的能量等级，Lx=[L×Ex/Emax]。Emax表示一个节点能量总量，Ex表示一个节点的剩余能量，将Emax均匀分成L份。

对于链路（x，y）∈E（G），定义 ERGxy=1n（Lx×Ly）来描述链路能量状态。这个新的度量具有以下突出的优点：①对称性，ERGxy=ERGyx=；②单调递增性，随着Ex，Ey增加而增加；③它的一阶导数单调递减；当节点处于较低的能量水平时，自变量变化导致ERGxy的变化量比在较高的能量水平时更大，所以ERGxy可以正确反映出链路（x，y）的状况。

定义的能量临界比值K，这意味着单跳邻域链路中的百分之K被认为是能量关键链路。能量临界值ERCcu与节点u∈V（G）有关，该值表示节点u的阈值，所以，只要NE（u）中某一链路的ERGxy小于ERCcu，就可判定该链路是能量关键链路。每个节点都有自己的能量临界值ERCcu。

算法设计思想是首先，准备节点u的单跳邻域拓扑，并且不使用能量关键链路；保留能量关键链路集合；然后，用非能量关键链路建立最小生成树，使用到克鲁斯卡尔算法；如果先前生成的最小生成树不包含所有节点，继续建立最小生成树。这个过程中，优先使用那些能量充足的链路；最后，生成一棵完整的最小生成树Tu，将u点的新邻域节点集合返回节点u。

并且对以下三种算法进行仿真，X-LMST，E-LMST，和LMST算法。参考文献比较了以下三项：网络的生存时间（是指网络中的第一个节点时能量耗尽的用时）；平均传输半径；平均节点度。

文献还对比了不同算法的平均网络生存时间，以节点密度为自变量。X-LMST算法表现最好。一般来说，三种算法的平均网络生命周期随节点密度的增加而增加。并且X-LMST的优势也随着节点密度增加而增加。这是因为，网络节点密度的增加可以提供更多的选择，以避免过度使用能源的关键链路。

然后，比较了不同算法的平均传输半径，以节点密度为自变量。传输半径定义为一个节点与其邻域节点集合中最远距离的节点之间的距离。平均传输半径是在网络中所有节点的传输半径的总和（按不同的算法）。X-LMST具有最高的平均传输半径。因为X-LMST允许保留一些长链接的节点，同时消除一些虽然短但是能源关键的链路，实现网络中的能量消耗平衡。

在平均节点度与节点密度方面，比较了不同算法的性能。最终得出X-LMST在三种算法中具有最大的平均节点度。

参考文献

[1]Shang D，Zhang B，Yao Z，et al.An energy efficient localized topology control algorithm for wireless multihop networks[J].Journal of Communications&Networks，2014，16（16）：371～377.

TN929.5

A

1004-7344（2016）17-0247-01

1 发展背景

2 算法介绍

2016-5-20

现有的拓扑控制算法主要集中在网络节点的低传输功率的分配问题上，同时保持全局连通。为了使每个节点学习到整个网络的状态信息，现有的算法不是结合全局网络状态信息，就是结合局部网络状态信息。前者的优势在于较低的发射功率，能更好的实现拓扑控制，并在小型网络表现出更好的性能，但是由于获取全局状态信息需要生成简化图，搜集和存储该类信息开销比较大，所以在实际情况下实现比较困难；而后者的优势在于以增加节点发射功率换取的高可伸缩性，并且，该算法允许每个节点独立的控制其局部拓扑，通过使用其邻域信息（在保持网络连接的同时）。然而，所有上述算法强调太多的网络的稀疏性，缺乏对网络中的节点和链路的能量临界状态的考虑。