一种基于WSN时变性与节点剩余能量均衡的机会路由算法

丁 男 谭国真 由 笛 张 伟

(大连理工大学计算机科学与技术学院 大连 116023)

1 引言

无线传感器网络(Wireless Sensor Network,WSN)，与移动Ad hoc网络和无线MESH网络一样，在很多重要领域被认为是一种方便的、经济的解决方案，比如交通监控、环境监测、军事安全等。

在实际应用中，多数用于 WSN的多跳路由算法是从有线网络中演变过来的。因此，在此类路由算法的设计过程中，往往需要假设 WSN是一个拓扑已知的网络，其通信链路是静态的、不变的。数据报文在利用该类路由算法进行传输过程时，是基于已建立好的路经进行传输的，没有考虑网络拓扑及各节点状态的动态变化[1,2]。

机会路由是近几年所提出的一种新的基于多跳的动态路由。文献[3]根据无线信道的衰减和干扰特性，认为WSN 中节点正确接收的数据报文服从一定的概率分布，并提出一种基于机会的传输方式，即当无线信道的条件合适时，无线节点才进行通信。机会路由机制可以提高数据报文在无线通信网络中传输性能，但是动态建立路径也给机会路由算法在设计上带来了难题[4]。

目前已有的工作主要集中在两方面研究。一方面是集中在为数据报文在传输过程中寻找基于WSN时变特性下的最短路径的策略与相应路由算法研究。文献[5]通过结合图论和网络流理论，针对最大网络流最短路径问题为机会路由的吞吐率建立了优化模型，为机会路由动态建立传输路径的相关研究提供了理论依据。文献[6]将数据包传输过程模仿蜜蜂采蜜的过程，设计了一个 RSSI(Received Signal Strength Indicator)机会路由算法，根据传输中各节点的信号强度动态调整节点的机会选择概率，以机会概率值选择报文所能到达的最佳节点进行数据转发。文献[7]引入蚁群优化算法，将 WSN中数据传输路径的动态选择，模拟蚂蚁觅食过程中在路径上残留的信息素诱导后面的蚂蚁尽快地找到到达目的地的过程。另一方面是以考虑网络中节点能耗问题为核心的动态路径建立策略及相应机会路由算法研究。文献[8]提出了两种考虑能耗的适用于机会传输的传输策略，一种是利用阈值判断的方法在动态建立传输路径时，排除网络中剩余能量少的节点，该策略适用于所有机会传输方式，另一种策略是针对无线传感器网络传输具有中心性的特点，将网络中节点以接收节点为中心，分成同心环型层次，在考虑剩余能量的基础上，使得各节点能量消耗分配更合理。文献[9]结合基于已建立传输路径整体的剩余能量问题，利用蚁群优化算法提出了一个EEABR(Energy Efficient Ant Based Routing)的路由算法。

分析上述研究，机会路由在动态建立路径过程中，网络传输的最短路径问题与网络节点剩余能量的均衡问题既相互影响，又相互制约。一些学者虽然考虑这两方面的关系，提出一些机会路由算法，主要是在考虑节点能耗的同时利用蚁群优化等启发式算法给出传输路径选择策略[10,11]。目前，缺少针对时变特性的网络路径优化与节点剩余能量均衡问题协同考虑的理论模型与分析方法。因为在考虑网络时变特性，传统静态网络相关理论是失效的[12,13]。

针对上述问题，本文结合热力学第2定律，在考虑网络中节点剩余能量以及在选择数据报文最优传输路径的时变性等因素前提下，对 WSN数据传输过程进行理论分析与描述，提出了机会熵模型，并以此为依据，结合蚁群优化(ACO)算法，提出了一个新的路由算法 ATDOP(ACO for Time Dependent Opportunistic-routing Protocol)。

2 网络模型与问题分析

2.1 网络模型

本文假设网络中各节点随机分布在一个矩形区域内，并且具有如下性质：(1)网络内Sink节点惟一，部署在网络中央位置，其余传感器节点部署后不再移动，并且各节点的地理位置信息不可知；(2)每个节点有惟一的标识；(3)所有节点平等，具有相同的计算、通信能力以及初始能量。

结合上面假设，给出网络模型的如下定义：

定义2通信距离。在图G中，通信距离，记为hu，表示节点u与Sink节点之间的通信跳数，用以表示距离Sink节点的距离。

定义3网络寿命。本文将从 WSN开始工作直到网络内第1个节点死去时，Sink节点所接收到的所有数据报文，其各自传输过程中到达Sink节点的跳数累计之和，定义为网络寿命。

定义 4节点o的邻居集，记为N(o)=ui(ui∈U,eoui∈E)，表示与节点o直接通信的节点ui集合。

2.2 时间依赖的最短路径

在图G中，任意节点o与Sink节点s之间路径(o,u1,…,ui,…,s)，为了能够让数据报文沿着向Sink节点接近的方向快速传递，根据文献[3]所提出的机会概率模型，在考虑网络的时变特性，我们提出了一个在节点o的邻居节点中选择下一跳节点方法。

式中hu代表u节点距离s节点的距离。wu(t)表示在t时刻，节点o与其邻居集合N(o)中节点u的通信权重，其值在实验中可根据随机概率模型获得，例如文献[4]，在实际应用中，可以通过测量信号强度获得。

为了便于描述与分析该问题，结合网络中基于时间依赖的最短路径的研究[13]，本文对机会路由的最短传输路径进行如下规划：

其中D(o,s,t)表示，在t时刻下，由源点o到目的点s的传输路径。

定理1在无线传感器网络中，采用机会传输方式的WSN是一个no-FIFO的网络。

证明假设该 WSN拓扑图G(V,E)，如图 1所示。其中V={o,u1,u2,u3,u4,u5,u6,u7,s},E={e(o,u1),e(u1,u2),e(u1,u3),e(u2,u3),e(u2,u4),e(u3,u4),e(u3,u5),e(u4,u6),e(u5,u7),e(u6,s),e(u7,s)}各节点从接收报文或产生报文，到将该数据转发给下一跳节点需要Δt时间。假设在t1时刻，由o节点发送一数据报文M1，在t1+Δt时刻，o节点发送M2。当M1达到u1时，u1选择u2作为M1的下一跳。当M1到达u2时，由于能量消耗等问题，u1,u2之间的通信权重发生变化，u1在转发M2时选择u3作为下一跳节点。而当M1到达u4时，u6节点由于网络拥塞或者故障等原因，u4选择u3作为下一跳节点，这样在t1+4Δt时，M1到达u3，而M2到达u5。最终，M2比M1早到s节点。M1经过的路径为Pa(M1)={o,u1,u2,u4,u3,u5,u7,s}，用时7Δt；而M2经过的路径为Pa(M2)={o,u1,u3,u5,u7,s} ，用时5Δt。因此，在考虑通信连路的时间依赖特性，采用机会传输方式的无线传感器网络的链路传输是no-FIFO的。 证毕

图1 网络通信图案例

定理2采用机会传输方式的WSN，其基于时间依赖特性的最短路径问题是一个NP难解问题。

证明根据定理 1，基于机会路由通信机制的WSN网络，其网络通信具有no-FIFO特性。 而文献[12]已证明，在时变网络中如果通信连路是 no-FIFO，其最短路径算法的复杂度是NP的。因此，在机会路由中，基于时变的最短路径问题是一个NP难解问题。 证毕

2.3 能量问题

(1)能量消耗矩阵 根据文献[14]无线传感器节点存在3个工作状态：空闲、发送和接收，我们建立能量消耗矩阵E为

其中各元素Eij，当i≠j，表示状态i转变成状态j所需消耗的能量，当i=j，表示节点在持续状态i时所消耗的能量。

(2)基于时间依赖的能量预测模型 根据上述能量消耗的能量矩阵，建立节点剩余能量的最优估计值Eop(t)：

其中El(t)表示当前节点剩余能量，可由节点实时获得；Es(t)表示t时刻，在i状态下，节点在T时间内能源消耗的预测值，其值基于能量消耗可能量矩阵E，根据式(6)计算而得，其中，T=2。

2.4 机会熵

1850年，德国物理学家鲁道夫·克劳修斯提出：在一个独立的系统中，能量密度的差异倾向于变成均等。这也是热力学第2定律的核心思想。并且定义熵(S)表示系统在不受外部干扰的情况下，系统通常往内部最稳定状态发展的特性。1872年，波尔兹曼进一步从分子运动的角度对克劳修斯的热力学熵理论进行了发展，进一步解释了系统由不稳定到稳定过程中，各分子的能量衰减过程，并提出了微观态的概念[15]，从微观的角度体现了一个物质系统中各分子能量的衰竭程度。通过比较各分子的熵值大小，就可以辨别出系统的转化方向，即往S值大的趋势发展。

这个现象可以用于描述数据报文在 WSN传输过程中，各节点状态以及剩余能量的变化趋势。根据热力学第2定律，将整个WSN看作是一个独立的、密闭的系统，我们通过定义机会熵，来描述每个WSN节点的状态。

定义5机会熵(opportunistic entropy)用Sop表示，它表征节点在自身能量有限并且能量不可再生的前提下，其自身状态的活跃程度，表示为

其中，剩余能量的最优估计值Eop(t)，由式(5)可得。wu(t)同式(3)。

3 基于蚁群算法的机会路由算法ATDOP

3.1 基于Sop的机会概率模型

根据传统蚁群优化算法中用信息素作为节点被选概率模型的思想[7]，结合机会熵Sop，本文提出了一个新的概率计算公式。

其中N(u)为u节点的邻居集，ui和uj分别为u节点邻居集中的节点；P(uj,t)为在第t时刻，蚂蚁将报文从节点u传递到下一节点uj的概率，即当前节点选择节点uj作为下一跳的概率；τ(uj,t)为在第t时刻下，节点uj上的信息素浓度；Sop(uj,t)为在第t时刻下，节点uj的机会熵；β为系统参数，它用来调整Sop(uj,t)对P(uj,t)中的影响程度，其值根据具体实验环境由经验设定，本文实验中β=1。基于式(8)，在传输过程中，选择P值最大的节点作为下一接收节点。

3.2 信息素更新

当节点u将数据报文发送给节点uj完毕之后，节点uj会自我更新信息素τ(uj,t)。由于信息素是决定蚂蚁选择路径的关键因素之一。因此，本文在提出信息素计算模型时引入了残留率ρ(t)。

其值与当前节点剩余能量相关，当节点能量剩余越少，ρ(t)值越小，意味着信息素的挥发越快。Einit表示节点初始能量值。通过根据能量调整残留率ρ(t)，可以使剩余能量少的节点的信息素挥发速度快。

初始化时，网络中各节点都被设置为相同的初始值；τ(uj,t-1)表示t-1时刻节点uj的信息素；Δτ(uj,t)表示第t时刻节点uj信息素的增加值，其值由式(11)可得

3.3 ATDOP算法

根据上述的信息素以及机会概率的计算模型，本文设计了基于蚁群优化算法的时间依赖机会路由协议算法(ATDOP)。其结构如图2所示。

(1)初始化 该状态下，由Sink节点通过泛洪的方式在网络内发送初始化信息，主要对算法中所需的各节点距离Sink节点的最短跳数h，信息素更新时间Tw，邻居节点集信息收集等待Tc，能量枯竭判断阈值ε，蚂蚁(数据报文)到达标志Fa,β, Δω等信息进行初值化。

图2 ATDOP结构图

(2)等待蚂蚁 一方面等待自身节点是否产生新蚂蚁要发送，如果有，则进行邻居节点的状态查询。另一方面监听网络，如果有邻居蚂蚁达到，判断该报文是否是查询节点状态，如果是，则返回自身节点状态(ID，机会熵Sop，信息素信息τ(uj,t))，然后再次进入监听状态；如果是需要转发的报文，则进行邻居节点的状态查询，为报文转发做准备。

(3)查询邻居节点状态 该节点会向邻居节点集N发送请求信息，在等待时间Tc内，收集邻居节点返回的各自Sop和τ(uj,t)，并计算机会选择概率P(uj,t)。

(4)选择节点 选择机会选择概率P(uj,t)最大的节点，建立传输路径，发送蚂蚁。

(5)信息素更新 信息素的自我更新，该状态主要有两个进入源：其一是在发送蚂蚁后立即自我更新，其二是在节点等待Tw时间后，进行自我更新(该处是对信息素的挥发处理)。

4 实验仿真与性能分析

4.1 仿真环境的建立

本文利用 NS-2 实验软件进行相关实验验证。仿真参数如表1所示。

表1 实验参数

4.2 性能分析与比较

本实验环节将ATDOP算法与以下两个路由算法进行比较：(1)基于传统的蚁群算法的路由算法，BACO(Basic Ant Colony Optimization)，文献[7,11]将传统的蚁群算法用在求解近似最短路由；(2)EEABR(Energy Efficient Ant Based Routing)路由算法[9]，该算法同样是基于蚁群算法，并参考了整体路径的剩余能量，剩余能量多的，将具有高的被选择机会。

在相同的仿真环境以及网络拓扑规模，根据本文中对网络寿命的定义，即当网络内任意一节点的剩余能量低于枯竭判断阈值ε时，实验停止。实验中，ε取能量初始值的10%。

(1)针对网络寿命，采用 BACO, EEABR和ATDOP 3个路由算法，分别进行了100次实验，结果如表2所示。

表2 平均网络寿命

传统的蚁群算法由于没有考虑节点的能耗，使得信息素高的节点被频繁选中传输信息，所以导致网络寿命最短；EEABR路由算法参考了路径中的节点的平均能量，并且在数据包到达Sink后再对整条路径上的节点一起更新，但该路径上个节点的剩余能量的没有单独考虑，虽然在网络寿命上有很大提高，但是仍略低于本文的ATDOP算法。

(2)针对各节点剩余能量的分布情况，我们同样统计了上述100次的实验结果，如图3所示，其中横轴为能量剩余率，纵轴为占节点总数比例。

BACO路由算法，由于蚂蚁在行进过程中没有考虑能量，信息的传输主要集中在最初所建立的近似最优路径上，能量的消耗也主要集中在这部分节点上，实验停止时只有 30%的节点剩余能量低于35%。而EEABR与ATDOP算法由于考虑到剩余能量问题，实验停止时大约70%以上的节点剩余能量低于能量初始值的35%。

(3)针对网络吞吐率，本实验将上述3个路由算法进行了100次的实验比较，其吞吐率分析如图4所示。

其纵轴为Sink节点接收到数据包，横轴为网络内各节点的累计跳数和，斜率即为该时刻所对应的吞吐率。3个路由算法在实验初期，其吞吐率接近，但随着实验的进行，由于传统蚁群算法没有考虑能耗，所以该算法的吞吐率比较稳定，而EEBAR与ATDOP由于考虑了节点的剩余能量，因此在实验后期，传输路径会动态地调整，跳数增多，二者的吞吐率都有下降，但ATDOP由于同时考虑了最短路径问题，因此其吞吐率好于EEBAR算法。

5 结论

本文在分析已有的机会路由算法的基础上，利用热力学第2定律对在时变特性下WSN网络数据报文的传输过程进行分析与描述，并参考热力学中熵的概念，以节点剩余能量和距离Sink节点的传输距离作为状态变量，提出了机会熵模型，并用以表征 WSN中各节点的传输状态。基于该模型，数据报文动态选择传输路径也就是选择机会熵小的节点作为转发节点。进而，本文将机会熵模型与蚁群优化算法相结合，提出了一个适用于时变网络模型的考虑网络资源负载均衡的机会路由算法(ATDOP)。最后，实验仿真表明，该路由算法相对于已有的基于原始蚁群算法的机会路由算法以及考虑能量的EEBAR机会路由算法的网络工作寿命更长，能量消耗的更均匀，网络资源分配的更合理。

图3 节点剩余能量的分布

图4 吞吐率

[1]Abhijeet B, Mohammad N, Javidi T,et al.. Adaptive opportunistic routing for wireless ad hoc networks[J].IEEE/ACM Transactions on Networking, 2012, 20(1):243-256.

[2]熊永平, 孙利民, 牛建伟, 等. 机会网络[J]. 软件学报, 2009,20(1): 124-137.

Xiong Yong-ping, Sun Li-min, Niu Jian-wei,et al.. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124-137.

[3]Sanjit B and Robert M. ExOR: opportunistic multi-hop routing for wireless networks[C]. Proceedings of ACM SIGCOMM, Pennsylvania, 2005: 133-143.

[4]Bo H, Pan H, and Kumar A. Mobile data offloading through opportunistic communications and social participation[J].IEEE Transactions on Mobile Computing, 2012, 11(5):821-834.

[5]Kai Z, Wenjing L, and Hongqiang Z. On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[C]. Proceedings of the IEEE INFOCOM, Phoenix, AZ, USA, 2008: 1490-1498.

[6]霍广城, 王晓东. 移动传感网中一种基于RSSI 的机会主义路由设计[J]. 电子学报, 2009, 37(3): 608-613.

Huo Guang-cheng and Wang Xiao-dong. An opportunistic routing for mobile wireless sensor networks based on RSSI[J].Acta Electronica Sinica, 2009, 37(3): 608-613.

[7]Paquereau L and Helvik E. Opportunistic ant-based path management for wireless mesh networks[C]. International Conference on Swarm Intelligence, Beijing, China, 2010:480-487.

[8]Lakshmi V, Kailas A, and Ingram A. Two energy-saving schemes for cooperative transmission with opportunistic large arrays[C]. Proceedings of IEEE GLOBECOM, Washington DC, USA, 2007: 1038-1042.

[9]Tiago C, Carlos C, Jorge S,et al.. An energy-efficient ant-based routing algorithm for wireless sensor networks[C].Ant Colony Optimization and Swarm Intelligence, 2006, 4150:49-59.

[10]宋超, 刘明, 龚海刚, 等. 基于蚁群优化解决传感器网络中的能量洞问题[J]. 软件学报, 2009, 20(10): 2729-2743.

Song Chao, Liu Ming, Gong Hai-gang,et al.. ACO-based algorithm for solving energy hole problems in wireless sensor networks[J].Journal of Software, 2009, 20(10): 2729-2743.

[11]Lee W. Ant-colony-based scheduling algorithm for energyefficient coverage of WSN[J].IEEE Sensors Journal, 2012,12(10): 3036-3046.

[12]Ariel O and Rapheal R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM, 1990, 37(3): 607-625.

[13]谭国真, 高文. 时间依赖的网络中最小时间路径算法[J]. 计算机学报, 2002, 25(2): 165-172.

Tan Guo-zhen and Gao Wen. Shortest path algorithm in time-dependent networks[J].Chinese Journal on Computers,2002, 25(2): 165-172.

[14]Al-Jarrah O and Megdadi O. Enhanced AODV routing protocol for bluetooth scatternet[J].Computers and Electrical Engineering, 2009, 35(1): 197-208.

[15]Pincus S M. Approximate entropy as a measure of system complexity[J].Proceedings of the National Academy of Sciences of the United States America, 1991, 88(6):2297-2301.