一种适用于异步无线传感器网络的机会路由机制*

王辛果

(中国西南电子技术研究所，成都 610036)



一种适用于异步无线传感器网络的机会路由机制*

王辛果**

(中国西南电子技术研究所，成都 610036)

无线传感器网络通常使用低占空比的异步睡眠调度来降低节点能耗。由于发送节点在接收节点醒来后才能向其发送数据，这将引入额外的等待时延。在最近的一些任播路由机制中，发送节点动态地选择最先醒来的候选节点转发数据，以最小化等待时延。但是，由于从最先醒来的候选节点到基站的时延可能并不低，任播路由机制并不一定能最小化端到端总时延。为此，提出了一种适用于异步无线传感器网络的机会路由机制，将路由决策建模为强马尔科夫过程，并根据最优停止理论推导出该过程一种简化的停止规则。仿真结果表明，节点到基站的最大端到端时延仅为基于地理位置的机会路由的68.5%。

无线传感器网络;异步睡眠调度;机会路由;低时延

1 引 言

无线传感器网络中的节点相互合作，将收集的数据通过多跳中继的方式传输至基站作进一步处理。由于节点通常仅由电池供电，如何降低节点能耗是无线传感器网络协议需要重点考虑的问题。在采用睡眠调度的介质访问控制(Medium Access Control,MAC)协议中，节点仅在有数据传输时才切换至活跃状态，无线通信模块在大部分时间内处于睡眠状态，能大幅降低节点能耗。

根据节点间是否需要时间同步，睡眠调度分为同步和异步两种。在同步睡眠调度中，相邻节点需要频繁地切换到活跃状态进行时钟同步。在异步睡眠调度中，每个节点独立地进行状态切换，节点在没有数据发送时，只需偶尔醒来一小段时间来确定是否需要帮助相邻节点转发数据。文献[1]指出由于占空比更低，异步睡眠调度在低流量网络中的能量效率更高。

在异步睡眠调度协议中，发送节点在接收节点醒来之后才能向其发送数据，这会引入额外的等待时延。最近的一些研究文献[1-2]利用无线传感器网络中节点高密度部署的特点，采用任播路由机制降低异步睡眠调度引入的等待时延。在任播路由机制中，每个节点维护多个候选的转发节点，并动态地选择第一个醒来的候选节点转发数据。如果每个节点有N个候选节点，任播路由的平均等待时延仅为传统的确定路由的1/N。与文献[3]为了提升路由可靠性而选择多个转发节点不同，任播路由每次只选择一个转发节点，不占用额外的网络容量。

由于没有考虑从各候选节点到基站这部分时延的差异性，任播路由虽能最小化每一跳的等待时延，但不一定能最小化整条路径上的端到端总时延。比如，任播路由可能会增加路径跳数，从而增加端到端时延。文献[4]考虑了异步睡眠调度的影响，设计了一种基于地理位置信息的机会路由机制。该路由机制使用节点的地理位置信息估计路径跳数，动态地选择第一个醒来且满足地理前进门限α的候选节点，并通过调整门限α对单跳等待时延和路径总跳数进行平衡，从而达到降低端到端时延的目的。但是，除了路径跳数和等待时延，实际的端到端时延还取决于路径质量、待传输数据包的大小等，所以该协议也不能最小化端到端时延。

本文为异步无线传感器网络设计了一种能最小化端到端总时延的机会路由机制。发送节点评估通过已醒候选节点转发数据到基站的总时延和等待更多候选节点醒来的额外时延，动态地决定何时停止继续等待以最小化总时延。由于各个候选节点醒来的时间随机，该路由决策过程被建模为强马尔科夫过程。采用最优停止理论推导出了路由决策过程的一种简化的最优停止准则。仿真结果表明，发送节点根据最优停止准则在异步调度的网络中进行机会路由能最小化端到端总时延。

2 系统模型

2.1 异步睡眠调度

假设除了基站一直处于活跃状态，网络中其余节点采用基于异步睡眠调度的MAC协议。如图1所示，当没有数据发送时，节点独立地在活跃和睡眠状态之间进行切换。节点在切换到活跃状态后首先广播发送信标消息向邻居节点通告本节点已经醒来[5]，并继续保持活跃一小段时间以确定是否有其他节点向本节点发送数据。当节点有数据发送时，切换到活跃状态，等待转发节点醒来接收数据。节点处于睡眠状态的时间是服从参数为λ的指数分布的随机时间ts。为降低能耗，节点的活跃时间一般极短，而睡眠时间相对较长。在采用异步睡眠调度的MAC协议中，节点之间不需要进行时钟同步，节点仅在有数据发送时的活跃时间较长，因而在数据流量相对较少的无线传感器网络中能大幅降低节点能耗。由于发送节点在接收节点醒来后才能向其发送数据，这将引入额外的等待时延[6]。

图1 异步MAC协议

Fig.1 Asynchronous MAC protocol

2.2 异步网络中的路由

在异步调度的网络中进行路由时，除了考虑转发节点的传统路径时延指标[7-8]，还应考虑到转发节点醒来的时间。转发节点醒来的时间越晚，数据转发过程中引入的等待时延也就越长。

如图2所示，假设发送节点s有N个候选转发节点，记为R={r1,r2,…,rN}，分别通过N个候选节点转发当前数据到基站的时延，记为TD={td1,td2,…,tdN}。由于采用异步睡眠调度，发送节点s不知道这些候选节点准确的醒来时间，只知道它们的睡眠调度参数λ。假设发送节点s在时间0有数据要发送，N个候选节点的醒来时间记为TW={tw1,tw2,…,twN}。如果节点s选择第i个节点，则节点s发送本次数据到基站d的期望总时延为tt=twi+tdi。

图2 路由决策

Fig.2 Routing decisions

如图3所示，在传统的确定路由机制[9]中，发送节点s选择td值最小的转发节点，不管该节点何时醒来，可能造成tw值太大；在任播路由机制[10]中，发送节点s选择tw值最小的转发节点，即最先醒来的节点，而不管该节点的td值大小。上述两种路由协议都只关注了时延的一方面，机会路由则是综合考虑TW和TD，动态地做出最优的路由决策，选择tt值最小的转发节点。

图3 路由机制比较

Fig.3 Routing schemes comparison

3 机会路由

3.1 路由过程

显然，发送节点应该从所有已经醒来的候选节点中选择td值最小的节点作为转发节点。发送节点等待的时间越长，醒来的转发节点越多，最终的td值越小，但tw值也越大。发送节点等待下一个候选节点醒来引入的额外等待时延期望值为(Nλ)-1。最优机会路由决策应根据候选节点的数量N、TD分布和睡眠参数λ，决定何时停止继续等待，以最小化端到端总时延tt。

将X(T)记为截止到时间T已经醒来的转发节点中最小的td值:

X(T)=min {tdi|i=1,2,…,M}。

(1)

式中：M是在[0,T]时间段内醒来的节点数。显然，X(T)是一个强马尔科夫过程。

最优机会路由应该最小化端到端总时延的期望值，即

minΨT=E[X(T)+T]。

(2)

如果发送节点s在时间0停止等待，此时没有任何候选节点醒来。因此，假设X(0)为极大值，这能保证发送节点必须至少等待一个候选节点醒来。

3.2 最优停止规则

由于转发节点醒来的时间TW为随机变量，可以将TD视为N个独立同分布的随机变量。根据最优停止理论，将式(2)进行简单推导后，可以得到

(3)

其中:

(4)

函数G(x)的物理意义是当已醒的候选节点中的最小td值为x时，继续等待更多节点能够获得的td下降值的期望;F是TD的概率分布函数。

定理1：下面的等式有唯一解:

G(X(T))=(Nλ)-1。

(5)

证明：如果G(X(0))<(Nλ)-1，则意味着第一个醒来的转发节点带来的td下降值比等待第一个节点醒来导致的tw增加值还小，这与X(0)为极大值的假设矛盾。因此，可以认为G(X(0))≥(Nλ)-1必然成立。由于G是非正的、连续的、严格递减的凸函数，所以等式(5)有唯一解，得证。

定理2：机会路由过程的最优停止规则为

X(T)≤η。

(6)

式中：η是等式(5)中关于X的唯一解。

证明：假设To是等式(5)中关于T的解。由于G(x)随x严格递减而X(T)随T不增，则G(X(T))随T不减。当T≤To时，NλG(X(T))-1≥0，ΨT随T不增；当T>To时，NλG(X(T))-1<0，ΨT随T不减。ΨT在时间To处取最小值，不等式(6)是最优停止规则，得证。

定理2表明，当X(T)≤η成立时，也即G(X(T))<(Nλ)-1时，应停止继续等待。该条件蕴含的物理意义是当继续等待能够获得的td下降值小于相应的tw增加值时，应该停止继续等待。

当X(T)≤η成立时，已醒的候选节点数服从参数为F(η)的几何分布，因而可以得到此时已醒节点数的期望值

(7)

和最优停止时间的期望值

(8)

进一步可以计算得到采用最优停止规则进行机会路由的端到端总时延期望值

(9)

4 仿真实验

发送节点经过候选转发节点转发数据到基站的时延，依赖于较多的随机变量，如每跳的等待时延、链路可靠性、候选节点数量等。因此，根据中心极限定理，可以认为TD大致服从正态分布。在网络运行过程中，发送节点s根据统计的历史信息估算TD的参数:

(10)

首先，在Matlab平台上进行数值仿真，验证最优停止规则的有效性。在仿真实验中，发送节点有20个候选的转发节点，每个转发节点的睡眠参数λ设为1，即每个节点平均每1s醒来一次。考虑两组实验场景，μ分别设为3和30。场景一中TD的均值相对较小，代表转发节点离基站较近或发送数据长度较小的情形；场景二中TD的均值相对较大，代表转发节点离基站较远或发送数据长度较大的情形。

每组场景各运行1 000次，将仿真结果取平均值。横轴为最优停止时间，单位为已醒节点数;纵轴表示的是发送节点到基站的端到端总时延，单位为秒。曲线的最低点表示路由过程的最优停止时间点。

场景一:σ分别为0.1和0.3。如图4所示，σ=0.1时，最优的唤醒节点数为2；σ=0.3时，最优的唤醒节点数为4。根据式(6)提供的停止规则进行路由时，唤醒的平均节点数分别为2.1和3.8，与最优的唤醒节点数极其接近，相应的端到端总时延分别为3.044s和2.916s。总体来看，由于μ并不比λ-1大多少，发送节点很快就会停止继续等待。μ相同的情况下，σ越大，各候选转发节点之间的td值差异越大，发送节点在路由时越值得等待更长时间。

图4 最优停止时间(μ=3)

Fig.4Optimalstoppingtime(μ=3)

场景二:σ分别为1和3。如图5所示，由于μ比λ-1大很多，路由时间相比场景一更长。具体来说，σ=1时，最优的唤醒节点数为7;σ=3时，最优的唤醒节点数为12。根据式(6)提供的停止规则进行路由时，唤醒的平均节点数分别为6.7和11.5，与最优的唤醒节点数极其接近，相应的端到端总时延期望值分别为29.07s和25.91s。同样，σ值越大，发送节点越值得等待更长时间。

图5 最优停止时间(μ=30)

Fig.5Optimalstoppingtime(μ=30)

接下来，通过NS2(Network-Simulationv2)网络仿真平台比较本文提出的机会路由与任播路由[10]、传统路由[9]、基于地理位置的机会路由[4]的端到端时延。不失一般性，在半径为1 000m的圆形区域内，随机部署800个通信半径为150m的节点，基站位于圆心位置。节点的睡眠参数设为λ=1，通信速率为250kb/s。为保持公平性，根据数据包大小，分为小数据场景(长度为103B)和大数据场景(长度为105B)。每条链路的丢包率为均匀随机生成，取值范围为0.05～0.2。

如图6所示，在小数据场景中，由于等待时延的权重高于数据传输时延，而传统路由没有考虑等待时延，其平均端到端时延远高于其他3种路由机制；在大数据场景，由于数据传输时延的权重高于等待时延，而任播路由没有考虑数据传输时延，其平均端到端时延最大。在上述两种场景中，本文提出的机会路由的端到端时延均小于文献[4]中的基于地理位置信息的机会路由。由于后者未考虑链路质量对时延的影响，这种优势在大数据场景中尤为明显，前者的最大端到端时延仅约为后者的68.5%。

图6 端到端时延比较

Fig.6 End-to-end delay comparison

5 结 论

本文首先介绍了异步睡眠调度机制及其对无线传感器网络的重要性;接下来设计了一种适用于异步无线传感器网络的机会路由机制,根据候选转发节点数、候选转发节点的睡眠时间参数、统计得到的转发时延分布动态选择下一跳转发节点;然后，将该路由决策过程建模为强马尔科夫随机过程，并推导出了一种简化的最优停止准则。仿真结果表明，机会路由能最小化发送节点到基站的端到端总时延。本文提出的机会路由机制有效且实现简单，具有较强的实用性。

[1] WU Y. Energy-efficient wake-up scheduling for data collection and aggregation[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(2)：275-287.

[2] MERLIN C J，HEINZELMAN W B. Duty cycle control for low power listening MAC protocols[J].IEEE Transactions on Mobile Computing,2010,9(11)：1509-1521.

[3] 夏辉,王辛果,杜晓明. 一种适用于军用无线自组网的可靠多径路由协议[J].电讯技术,2014,54(11)：1549 -1553. XIA Hui,WANG Xinguo,DU Xiaoming. A reliable multipath routing protocol for military wireless ad hoc networks[J].Telecommunication Engineering,2014,54(11)：1549-1553.(in Chinese)

[4] NAVEEN K P，KUMAR A. Relay selection for geographical forwarding in sleep-wake cycling wireless sensor networks[J].IEEE Transactions on Mobile Computing,2013,12(3)：475-488.

[5] SUN Y,GUREWITZ O,JOHNSON D B. RI-MAC:a receiver initiated asynchronous duty cycle MAC protocol for dynamic traffic load[J]//Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems. Raleigh,USA：IEEE,2008：1-14.

[6] LI Z J,LI M O,LIU Y H. Towards energy-fairness in asynchronous duty-cycling sensor networks[J]//Proceedings of IEEE INFOCOM 2012. Orlando,USA：IEEE,2012：801-809.

[7] NITHYA R，MAHENDRAN N. A survey:duty cycle based routing and scheduling in wireless sensor networks[J]//Proceedings of 2015 IEEE International Conference on Electronics,Circuits,and System.Cairo,Egypt：IEEE,2015：813-817.

[8] ABRARDO A,BALUCANTI L,MECOCCI A. Distributed duty cycling optimization for asynchronous wireless sensor networks[J]//Proceedings of 2012 IEEE International Conference on Communications.Ottawa,Canada：IEEE,2012：637-641.

[9] LIU K，ABU-GHAZALEH N. Stateless and guaranteed geometric routing on virtual coordinate systems[J]//Proceedings of IEEE MASS 2008. Atlanta,USA：IEEE,2008：340-346.

[10] KIM J. Optimal anycast technique for delay-sensitive energy-constrained asynchronous sensor networks[J].IEEE Transactions on Networking,2011,19(2)：484-497.

王辛果(1983—)，男，四川遂宁人，2011年于中国科技大学获工学博士学位，现为工程师，主要研究方向为战术数据链、无线自组网等。

WANG Xinguo was born in Suining,Sichuan Province,in 1983. He received the Ph.D. degree from University of Science and Technology of China in 2011. He is now an engineer. His research concerns tactic data link,wireless ad hoc networks,etc.

Email:xinguowang911@163.com

An Opportunistic Routing Scheme for Asynchronous Wireless Sensor Networks

WANG Xinguo

(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

Wireless sensor networks usually adopt low duty-cycle asynchronous sleep schedule to reduce energy consumption of node. Since a sender can’t send data packet until the receiver wakes up,additional waiting delay will be introduced. In some recent anycast routing schemes,a sender dynamically selects the first candidate to wake up to forward data packet,in order to minimize the waiting delay. However,the delay from the first candidate to the base station may not be low,so anycast routing can not necessarily minimize the total end-to-end delay.For this problem,an opportunistic routing scheme is proposed for asynchronous wireless sensor networks,where routing decision is modeled as a strong-Markov process and a simplified stopping rule of this process is derived through optimal stopping theory. Simulation results show that the maximal end-to-end delay from the sender to the base station is only 68.5% of the opportunistic routing based on geographical location.

wireless sensor networks;asynchronous sleep schedule;opportunistic routing;low delay

10.3969/j.issn.1001-893x.2016.07.006

王辛果.一种适用于异步无线传感器网络的机会路由机制[J].电讯技术，2016,56(7):750-754.[WANG Xinguo.An opportunistic routing scheme for asynchronous wireless sensor networks[J].Telecommunication Engineering,2016,56(7):750-754.]

2016-03-23；

2016-06-06 Received date:2016-03-23；Revised date：2016-06-06

TN915.04;TN923

A

1001-893X(2016)07-0750-05

**通信作者：xinguowang911@163.com Corresponding author：xinguowang911@163.com