应急多跳无线网络中的移动性研究∗

张康荣 林基明 郑 霖

（桂林电子科技大学信息与通信工程学院 桂林 541004）

1 引言

在应急的移动多跳无线网络中，每个节点可能有几个相邻节点［1］。网络中的节点必须通过允许并发传输和调整传输功率来决定最优的通信链路。而选择用于建立链路的邻居节点子集则是多跳网络拓扑控制的主要目标［2～3］。

已有文献基于同时满足最优传输范围和减少干扰对多跳网络的拓扑控制进行了研究。研究成果表明较低传输功率的移动节点将导致网络被分割，而较高传输功率的移动节点又通常会引起通信干扰，影响整体网络容量［4～5］。因此需要对移动节点的拓扑连接进行必要控制。目前在拓扑控制中的大多数研究都没有考虑到节点迁移，而是使用了一个用于网络分析的静态拓扑模型［6］。

文献［7］中提出了一种基于方向信息的多跳无线网络的分布式拓扑控制算法。该算法基于相邻节点进行了传输功率的优化控制，降低了干扰，提高了可靠性。但是该算法并没有解决网络拓扑控制的问题。文献［8］针对网络中的每个节点根据局部邻域和信道传播模型信息计算出了强连通的拓扑。文献［9］对静态网络拓扑控制算法进行了改进，使其能够适应移动。文献［10］提出了链接信息无拓扑（LINT），LINT算法利用节点度信息自适应地调整传输范围，保持了静态网络中的连通性和双连接性，但是该算法不能有效对节点的传输功率进行调节。

基于上述问题，本文提出一个提高应急多跳无线网络的接入移动节点的能力的方法。首先针对节点迁移导致网络拓扑动态变化的问题，通过利用非随机移动模式，使得每个节点都可以预测邻域拓扑的未来状态，从而达到每个邻居所需的最小传输能力。其次基于单跳邻居的估计最小功率信息的最优传输功率选择产生具有较强抗干扰性能的网络拓扑。这种网络拓扑结构是通过多跳通信保持连通性并因此保持网络的整体覆盖区域的拓扑结构。最后通过仿真测试对所提出的算法在保持有效传输功率的同时是否能够可靠保持移动节点的连通性进行验证。

2 基于移动节点感知的拓扑控制思路

基于移动节点感知的拓扑控制算法分为两个步骤。首先，每个节点通过最大传输功率（Pmax）发送HELLO数据包，以了解邻居拓扑的未来状态。信息包包含节点的预测位置，以及在稍后的某个时间点与它的单跳邻居通信所需的最小传输能力列表［11～12］。其次，每个节点选择一个最优的功率级（Poptimal），这样就可以通过一个要求更低的传输功率级来达到要求更高的传输功率的邻居［13～14］。

算法主要思路如图1所示。

图1 拓扑控制算法主要过程

在图1（a）中，描绘了在某个任意时刻（t0）的初始拓扑结构。此时HELLO数据包以最大的发射功率在邻居之间交换。图1（b）显示了节点在时间（t0+α）的预测未来位置。节点5、4、3和2可以直接相互到达。图1（c）表示了传输功率调整后的拓扑结构。其中每个节点调整了到达其邻居所需的功率，以保持其连通性。例如，节点2计算节点5、4、3和1所需的功率，并依据计算结构建立了与节点3和1的链路。

3 拓扑控制和最优功率算法

3.1 拓扑预测和传输功率计算

在t0时刻，每个节点计算在t0+α时刻到达下一跳邻居所需的最小传输功率的列表。t0和t0+α分别表示当前时间和下一跳时间，其中α是以s为单位的单位时间增量。下面对最小传输功率列表的计算方法进行阐述。

一个节点用以下两个方程来基于当前位置、速度和方向预测其的未来位置：

其中（x(t0+α)，y(t0+α)）表示一个节点在 t0+α时刻的位置，s是以某个最大值为界的当前速度，θ是节点的移动方向。

接下来，使用式（3）计算其与下一跳邻居在t0+α时刻的距离。假设有两个相邻节点，即节点A和节点B，则：

最后，我们可以利用双射线地面路径损耗模型来预测基于无线传播模型的任意两个节点间隔距离上的平均信号强度Pr：

假设发射功率Pt和节点A、节点B之间的预测距离d( )t0+αAB是已知的，则使用式（4）可以计算出节点A与节点B之间的所需的最小传输功率。

3.2 最佳功率选择

在接收HELLO数据包时，每个节点对拓扑映射进行预测，以确定与下一跳邻居进行连接所需的最小传输功率。每个节点通过维护两个数据结构来构造这个拓扑映射：1）局部视图列表L包含两个字段：下一跳邻居的标识和最小的功率；2）扩展视图列表E包括下一跳邻居的标识、下两跳邻居的标识和估计的传输功率［15～16］。

算法利用局部视图和扩展视图列表，选择了一个最优的功率Poptimal，这样就可以通过一个中间邻居节点来达到要求更高传输功率的邻居。通过比较节点自身的传输功率和最近邻的传输功率，实现了对Poptimal的选择。如果最近的邻居不覆盖远处的邻居，算法会搜索另一个具有较高传输能力的邻居，这样所有邻居之间的连通性就会被保留。寻找最优功率的算法流程如图2所示。

图2 最优功率算法

一个基于最大传输功率的拓扑以及基于所提出的最优功率选择算法构建的传输拓扑网络的示例如图3所示。

图3 最优功率算法的效果

图3中示例中基于二维地面反射模型在512×512m2区域上均匀分布的25个节点。图3（a）描述了最大功率（18dBm）的拓扑结构，其近似传输距离为170m，即在没有拓扑控制的情况下，每个节点的邻居密度平均为8.08。图3（b）是基于最优功率构建的拓扑控制网络，其平均传输功率为12.07dBm，平均邻域密度为4.88，因此在保持网络连通性的前提下，该拓扑具有较低的局部邻域密度和传输功率。显然，图2（b）所示拓扑网络中的节点需要更少的传输功率。

4 仿真验证

使用网络模拟器NS2实现本文上述算法，并将本文算法与纯洪泛算法（无发射功率控制）和局部信息无拓扑算法（LINT）进行比较。

洪水算法使用默认的传输功率级（即24.5 dBm）。另一方面，在节点度的基础上进行传输功率调整。如果邻居的数量少于6个，我们就会在全功率下运行LINT算法，随着节点度的增加逐渐减少传输功率。移动节点被设置为有6个功率级，分别为 24dBm、21dBm、18dBm、13dBm、7dBm和-3dBm，这些功率级分别对应250m、210m、170m、130m、90m和50m的传输距离。表1总结了NS2中使用的所有参数的值。

表1 网络模拟器NS2的参数设置

利用两种非随机网络迁移模型，即确定性和半确定性的移动模型。1）在确定性迁移模型中，节点运动的偏差设置为零。2）在半确定移动模型中，偏差从-15°变化到+15°，因此节点运动在30°的柱状宽度上变化。基于对CMU版本的NS2程序的修改，以生成仿真实验的模拟场景。

4.1 仿真环境

在仿真模型中，节点被随机放置在1000×1000m2的网格中。所有节点从1m/s移动到最大速度为20m/s，暂停时间设置为0。整个模拟持续时间为300s。在仿真实验中，网络大小从50个增加到150个，每增加25个节点。在性能评估中使用了以下指标：1）平均开销，定义为每个节点每个数据传输接收的数据包的数量。2）平均传输功率，为总传输功率与网络大小之比，其中，HELLO数据包仅包含在本文算法和LINT中。3）延迟，是指从源节点发送的数据和预期目的地接收到的数据之间的时间。

4.2 仿真结果

首先对网络中广播数据包的开销进行监测。图4（a）和（b）分别绘制了每个节点传输的平均开销，并将节点的总数量作为确定的和半确定性移动模型的网络大小的函数。其中图4（a）是移动模型下的不同节点数量的无线网络的广播数据包的平均开销；图4（b）则是半移动模型下的平均开销。

图4 节点广播的平均开销对比

由图4可知，本文算法的平均开销始终低于基本算法和LINT算法。如前一节所述，应用拓扑控制的效果显著降低了局部节点的平均密度，从而减少了相邻节点转发数据包的结果。这也有助于降低节点传输的功率，因为它通常会转发较少数量的中间节点的包。LINT算法也是利用传输功率优化调整实现多跳无线网络的拓扑控制，但是该算法只要监测到网络连接性变差，节点就会转向最大功率传输模式。因此两种移动模型的开销在较大规模的无线网络中是接近的。

图5（a）和（b）表示两种移动模型的平均传输功率。其中图5（a）是移动模型下的不同节点数量的无线网络在保持节点连通性前提下的平均传输功率；图5（b）则是半移动模型下的平均传输功率。

图5 节点平均传输功率的对比

图6 节点平均延时的对比

由图5可知，本文所提出的算法能够以最小的功率保持与在传输范围边界上的节点的连通性，而LINT在这种情况下运行在更高的传输功率级。对于较小的网络，LINT必须增加一些孤立节点的能力。半确定性移动模型的功耗比确定性模型要高，这是为了补偿相邻节点的有限偏差。

图6（a）和（b）为本文算法和其他算法分别在移动模型和半移动模型下的平均延迟。

由图6可知，两种移动模型的延时在所有的算法中都是相似的，并且在节点数量较少的网络中本文算法的延时相对较高。在网络密集的情况下，所有算法的延迟时间都相对较高。而在适度的流量负载下，非拓扑控制网络的延时相对较低，因为与拓扑控制的网络相比，在网络中传播数据包需要较少的跳数。

5 结语

本文提出了一种新的基于移动节点的拓扑控制算法。我们的方案利用非随机节点移动模式来预测网络拓扑的未来状态。每个节点都运行一个分布式算法来估计成功地与每个邻居进行通信所需的最小功耗。最后，节点将其传输功率调整到最优级以实现鲁棒拓扑。仿真结果表明，本文算法支持节点间的多跳通信，以有效地利用有限的系统资源，如动态无线环境中的功率和带宽。此外，由于我们的协议运行在一组离散的功率级别上，因此位置信息不需要非常精确。本文算法的基础是一个单跳的HELLO数据包，因此网络中的节点必须定期发送附加的邻居信息的数据包，这对网络负载会产生一定影响。