移动自组织网路由稳定性分析

郭建立，刘 刚

（1.北京邮电大学，北京100876;2.中国电子科技集团公司第五十四研究所，河北石家庄050081;3.燕山大学电气工程学院，河北秦皇岛066004）

0 引言

在移动自组织网络环境中，节点的自由移动导致网络拓扑结构变化频繁，用于数据转发的路由寿命相对于传统有线网络极其短暂。在动态网络环境中选择一条稳定的路由能够有效地减少网络路由重建和维护过程所需的带宽和能源消耗、避免对网络中其他节点的正常数据传输产生干扰[1-3]，并能够提供更好的QoS需求保障，这在网络资源和能源供应都极其有限的移动自组织网络中尤其重要[4]。该文分析了移动自组织网络中节点的动态特性与其局部拓扑结构变化程度之间的关系，提出了一种利用局部拓扑结构变化的不确定性程度刻画移动节点动态特征的稳定路由选择策略，并利用信息熵的特性对局部拓扑结构变化的不确定性程度给以定量的度量。

1 熵度量

1.1 局部拓扑变化动态特征

在包含n个节点的移动自组织网络中，某一时刻t的网络拓扑结构可以表示为一个无向图Tt=〈V，Lt〉，其中V={N1，N2，…Nn}是网络中所有节点的集合，Lt是t时刻网络中状态为连通的所有逻辑链路组成的集合。

定义1:节点D在时刻t的局部拓扑结构信息由节点D、节点D的邻居，以及它们间的逻辑链路组成，表示为其中为t时刻节点D所在局部拓扑空间内所有节点的集合为t时刻局部拓扑空间内存在的所有逻辑链路的集合。

局部空间内的逻辑链路可以划分为2种:一类是节点D与其所有邻居节点间存在的链路，这类链路的变化程度能够反映动态网络环境中节点D的邻居节点的变化特性;另一类是节点D的所有邻居节点之间的链路，这类链路的变化能够反映局部范围内邻居节点彼此之间以及邻居节点与节点D之间拓扑结构变化的动态特征。

1.2 局部拓扑变化熵度量

在信息论中，熵[5]作为随机变量的自信息，用来度量一个随机变量自身所具有的不确定性程度，一个离散型随机变量X的熵定义为:

式中，χ为离散型随机变量X的取值空间;p（x）为随机变量X的概率密度函数。

记Si为节点k局部拓扑结构变化过程中的一个状态，各状态元素按时间顺序构成一个有序序列:

可用一对离散随机变量S和R作为局部拓扑结构变化序列的特征向量来表示节点的动态特征:S表示局部拓扑结构状态的变化，取值空间为ST（k），其概率密度函数为:

式中，R表示各状态在SN（k）序列中的实际分布。如果将SN（k）序列中连续出现的同一个状态形成的子序列称为一个子游程，则可以将SN（k）序列表示为游程序列形式RN（k）:

令LEN（Ri）为子游程Ri的长度，将RN（k）序列表示为概率形式，其概率密度函数为:

在RN（k）序列中有通过以上计算结果可以分别计算SN（k）和RN（k）的熵:

若将SN（k）、RN（k）视为局部拓扑状态变化过程中2个独立的随机特征向量，则根据信息熵的链式法则，节点k局部拓扑结构变化的不确定性程度H（TN（k））可以由下式计算得到:

1.3 路由稳定性度量

在移动自组织网络中，一条从源节点S到目的节点D的路由Path（S，D）的稳定程度可以由该路由上所有转发节点的稳定程度来共同反映，通过以下2个参数来描述:

式中，Htotal（S，R）为Path（S，D）中所有转发节点局部拓扑变化熵的和;Hmin（S，R）为Path（S，D）中瓶颈节点的稳定程度。显然，路由的长度以及转发节点的稳定程度都将对Htotal（S，R）的值造成影响，因此那些跳数少并且转发节点较稳定的路由具有更小的Htotal（S，R）值。

1.4 RODSR路由协议

为了定量评估该文所提出的稳定路由选择策略，对源动态路由协议（Dynamic Source Routing Protocol，DSR）进行了必要的扩展，提出了一种基于逆向优化的源动态路由协议（Reverse Optimized Dynamic Source Routing Protocol，RODSR）。RODSR对DSR协议的路由建立过程进行了部分改进，其目的是验证局部拓扑变化熵度量对路由协议性能的提升。

在RODSR中，每个节点需要维护一个两跳邻居列表以实现逆向路由优化，其操作过程与DSR协议基本相同。为了实现路由的逆向优化操作，需要扩展DSR协议的RREQ分组，使其携带节点的最新稳定性测度信息，以及节点所维护的邻居节点信息。当RREQ到达目的节点时，由目的节点结合RREQ中获取的路由信息和本地维护的邻居列表信息对路由进行优化。

2 仿真实验及结果分析

2.1 仿真实验

使用NS2.31仿真软件对协议进行仿真，节点移动模型采用随机点模型（Random Waypoint Model，RWM），仿真区域设置为1800×900m2的矩形区域，仿真过程中的其他参数设置如表1所示。

表1 仿真参数设置

2.2 仿真结果分析

在仿真过程中，针对不同网络环境下的分组成功递交率和端到端分组时延，对DSR和RODSR协议进行了比较。

图1比较了DSR和RODSR协议的分组递交成功率。从图1（a）中可以看出，在节点移动速度缓慢的网络环境中，RODSR协议的分组递交成功率提高并不明显，这是因为相对于节点的无线传输覆盖范围，节点移动所导致的拓扑变化较缓慢，节点间拓扑变化的不确定程度差异较小。但是，随着节点移动速度的增加，节点间拓扑变化程度的差异加剧，RODSR协议的性能有明显提升。

从图1（b）中可以看出，在节点密度较小的情况下，RODSR协议的分组递交成功率仅有小幅提高，这是由于共同邻居数较少，使得RODSR协议的优化机会减小。但是，随着节点密度的增加，RODSR协议可利用的优化节点数开始增多，从而使得协议的性能较DSR协议有较大提升。

图1 分组递交成功率性能对比

图2比较了2种路由协议的端到端分组时延。可以看出RODSR协议的端到端延迟相比于DSR协议具有比较明显的降低，还可以看出网络负载对网络的端到端延迟也具有明显的影响。

图2 端到端延迟性能对比

3 结束语

基于局部拓扑结构变化的熵度量方法能够对局部拓扑结构变化的不确定性程度给以定量的度量，适用于在动态网络环境中选择相对稳定的路由。该方法提升了移动自组网路由协议的性能，能够有效降低网络开销，提高有限网络资源的利用效率，并延长网络的生命周期。

[1]SU，LEE SJ，GERLA M.Mobility prediction and routing in ad hoc wireless networks[J].International Journal of Network Management，2001，11（1）:3-30.

[2]LENDERS V，WAGNER J，HEIMICHER S，etal.An empirical study of the impact of mobility on link failures in 802.11 ad hoc network[J].IEEE Wireless Communications，2008，15（6）:16-21.

[3]刘刚，郭建立，崔刚，等.移动自组织网络环境中负载均衡策略研究[J].无线电工程，2010，40（7）:1-3.

[4]ZHANG H，DONG YN.A novel path stability computation model for wireless Ad Hoc networks[J].IEEE Signal Processing Letters，2007，14（12）:928-931.

[5]CHANNON CE.A mathematical theory of communication[J].The Bell System Technical Journal，1948（27）:379-423，623-656.