WSNs中基于剩余能量的机会路由协议

吕晓军，王小书，贾新春，陈瑞凤，李建玉+

(1.中国铁道科学研究院 电子计算技术研究所，北京 100081；2.山西大学 数学科学学院，山西 太原 030006)

0 引 言

由于机会路由协议提高了网络数据包传输的可靠性并减少了由于数据包重传所引起的不必要的能量消耗[1,2]，因此，近几年来，机会路由协议已经获得了国内外许多学者的关注和研究[3-5]。

机会任意路径转发(OAPF)协议[6]采用期望任意路径传输次数(EAX)作为其路由指标。EAX指标充分利用了数据传输过程中可能存在的多条路径，从而使其可以有效的用于机会路由协议的数据转发过程中。在文献[7]中，一个能量有效的机会路由协议(EEOR)被提出，它使用期望成本路由指标来计算数据传输过程中的成本。文献[8]提出的机会路由协议以传输节点与移动目的节点之间的距离作为路由指标，并通过计算网络期望时延来选择合理的转发节点。文献[9]提出了一个可靠的并且能量有效的机会路由协议，该协议使用剩余能量和期望成本的比值作为它的路由指标。一个基于功率控制的协同机会路由协议在文献[10]中给出，它通过研究数据转发机制的有效性来减少节点的能量消耗。

在现有的机会路由协议的设计中，所考虑的路由指标往往是固定不变的，因此，这些指标可以用于候选节点集的选择算法。但是，在实际的应用场景中，往往需要用一些变化的指标来作为节点的路由指标，如节点的剩余能量和节点状态等。现有的路由协议中，针对这种变化的路由指标所设计的候选节点选择算法还比较少。为此，本文提出了一个度量指标——剩余传输次数指标，并且提出了一个以节点剩余能量为路由指标的机会路由协议。这个路由协议采用剩余传输次数指标来对节点的候选节点集进行选择。

1 网络模型及准备

1.1 网络模型

我们考虑一个由n个节点组成的无线传感器网络并假设所有的节点都有一个唯一的身份标识，即i∈[1,n]。这个无线传感器网络可以建模为一个有向通信拓扑图G=(V,E,W)。其中，V是所有节点的集合，即|V|=n，E是所有通信链路的集合，W表示每一个节点出度的上界，即节点可拥有的最大子节点的个数。每条通信链路都有一个误差概率，表示为e(u,v)，其中u，v分别表示链路两端的传感器节点。1-e(u,v)表示节点u沿着链路(u,v)成功发送一个数据包到节点v的概率。

本文所考虑的无线传感器网络模型包含一个源节点，一个目的节点以及若干个中继节点，其中，源节点负责采集数据，并将数据发送给邻近的中继节点或者目的节点；目的节点负责收集来自源节点和中继节点的数据；中继节点负责接收来自源节点或者其它中继节点的数据，并对这些数据进行处理和转发。

图1所给的是采用机会路由协议的无线传感器网络模型，其中，s为源节点，V1～Vn表示中继节点，d表示目的节点。在图1中，源节点s的候选节点集为{V1,V2,…,Vn}。源节点s发送的数据包可以被其候选节点集中的节点接收，然后由候选节点集中优先级最高的节点来对数据包进行转发，从而有效地利用潜在的路径来增加网络传输的可靠性，减少数据包的重复传输。

图1 无线传感器网络模型

本文所考虑的无线传感器网络是以轮的方式来对源节点采集的数据进行收集的。网络生存周期定义为当网络中有一个节点失效时网络所运行的轮数。

1.2 准 备

为了更好说明本文所提的基于剩余能量的机会路由协议，我们首先给出了如下的假设。

假设：候选节点集中的候选节点回复的应答包可以100%的被发送节点和其它候选节点接收到。

注：这是一个常常被用到的假设，事实上，候选节点可以通过多次发送应答包来近似的认为所发送的应答包可以被发送节点和其它候选节点100%接收[7]。

网络发送和接收数据包的一阶能量消耗模型给出如下[9]

Etx(k,r)=Eeleck+kεampr2

(1)

Erx(k,r)=Eeleck

(2)

其中，k表示发送的信息量，单位为比特，r表示传输距离，Eelec表示电路元器件发送和接收1比特数据所消耗的能量。εamp表示功率放大器发送每比特数据的能耗系数。在本文中，传输损耗指数设置为2。Etx(k,r)和Erx(k,r)分别表示发送和接收k比特数据所消耗的能量。

2 基于剩余能量的机会路由协议

2.1 剩余传输次数

在现有的一些机会路由协议设计中，候选节点集的选择往往与一些固定的路由指标相关联。在这里我们以OAPF机会路由协议所采用的EAX路由指标为例进行说明。

EAX指标表示由发送节点到目的节点的期望任意路径传播次数，它的数学表达式给出如下

EAX(s,d)=S(s,d)+Z(s,d)

(3)

(4)

(5)

其中，s表示发送节点，d表示目的节点。A表示发送节点s的候选节点集，候选节点集中的节点按照各自的EAX指标从小到大进行排序，并编号为1到|A|，pj表示由发送节点s发送数据包到编号为j的候选节点的成功率。S(s,d)表示节点s发送数据包到候选节点集A中，并且至少有一个候选节点接收到数据包的期望传输次数。Z(s,d)表示由节点s的候选节点集A中的节点转发数据包到目的节点的期望传输次数，其中，由于候选节点的EAX指标是固定的，因此，Z(s,d)的计算考虑了候选节点集中节点关于EAX指标的优先级。

然而，在许多的实际应用中，节点的剩余能量被用在机会路由协议中的路由指标中[8]。节点的剩余能量是随着网络的运行在不断变化的，因此，它很难像EAX指标一样被选择作为候选节点集的一种选择标准。为此，我们提出了一种新的度量指标——剩余传输次数(RTX)，使用它来进行候选节点集的选择。

我们考虑如图2所示的两种情形。在图2(a)中，节点s包含3个候选节点，分别为V1，V2和V3。在数据包传输过程中，由于节点V1，V2和V3的剩余能量是不断变化的，因此，这3个节点在转发数据包上的优先级也是不断变化的。在图2(b)中，由于目的节点d是节点s的候选节点，因此，在数据包转发上，目的节点d始终拥有最高的优先级，节点V1和V3根据各自的剩余能量来确定各自的优先级。

图2 RTX度量指标设计的两种情况

我们首先考虑图2(a)所示的情形，即节点的邻居节点集中没有目的节点的情形。假设A是节点s的候选节点集，则节点s的RTX指标RTX(s,d)可以计算如下

RTX(s,d)=S(s,d)+Z(s,d)

(6)

(7)

(8)

其中，候选节点集A中的节点被随机的编号为1到|A|，pj表示由发送节点s发送数据包到编号为j的候选节点的成功率。S(s,d)表示节点s发送数据包到候选节点集A中，并且至少有一个候选节点接收到数据包的期望传输次数。Z(s,d)表示由节点s的候选节点集A中的节点转发数据包到目的节点的期望传输次数，它是候选节点集中节点RTX指标的加权平均值。

考虑图2(b)所示的情形，即节点的候选节点集中包含目的节点。由于目的节点在任意候选节点集中总是拥有最高的优先级，而在式(8)的计算过程中，候选节点集中的节点是没有优先级的，因此，采用式(8)来表示节点s的候选节点集中的节点到目的节点d之间的传输次数是不合适的。为此，我们将式(8)重写为

(9)

在这里，我们假设目的节点d在候选节点集A中的编号为|A|，即p|A|表示由节点s发送数据包到目的节点d的成功率。节点s发送数据包到候选节点集A中，并且至少有一个候选节点接收到数据包所需要的期望传输次数为S(s,d)。因此，在式(9)中，候选节点集A中目的节点d接收到数据包的概率为(1-p|A|)S(s,d)-1p|A|，而目的节点没有接收到数据包的概率为(1-p|A|)S(s,d)。如果目的节点d接收到数据包，则不需要对数据包进行转发，剩余传输次数为0。而如果目的节点d没有接收到数据包，则由候选节点集A中的其它节点对数据包进行转发的剩余传输次数为

(10)

这里，Z(s,A-{d})表示由节点s的候选节点集A-{d}中的节点发送数据包到目的节点的期望传输次数。由条件概率公式可知，由节点s的候选节点集中的节点发送数据包到目的节点d的期望传输次数为(1-p|A|)S(s,d)-1p|A|·0+(1-p|A|)S(s,d)·Z(s,A-{d})。

2.2 寻找最优候选节点集

在本文中，RTX指标被用来选择节点的候选节点集。在基于剩余能量为路由指标的机会路由协议中，通过最小化节点的RTX指标可以有效减少节点传输到目的节点的传输次数，从而减少不必要的能量消耗。

算法1给出了一个节点s的最优候选节点集选择方法以及其自身RTX指标的计算方法。算法1的工作流程如下：首先初始化节点的候选节点集C为空集，且RTX(s,C)=∞。这里RTX(s,C)表示节点s以C为候选节点集时的RTX指标。然后从节点s的邻居节点集N(s)中任选一个子集Ω，该子集中的元素个数不能大于节点的出度W，即|Ω|≤W。接下来计算RTX(s,Ω)。这样遍历的寻找一个子集Ω，使得RTX(s,Ω)最小。最后所得到的子集Ω就是节点s的最优候选节点集C，节点s的RTX指标为RTX(s,C)，即RTX(s,d)=RTX(s,C)。

算法1： 候选节点集选择算法

Input： the RTX metrics of all neighboring nodesN(s),the destination noded.

Output： the candidate set of the nodesand its RTX metric.

(1) LetCbe the set that represents the candidate of the nodesandC←Ø,RTX(s,C)←∞;

(2) LetΩbe a set andΩ←Ø;

(3)fori=1：Wdo

(4)forΩ← any i number of nodes∈N(s)do

(5)ifd∈Ωdo

(6) calculateRTX(s,Ω) by (6),(7),(9);

(7)else

(8) calculateRTX(s,Ω) by (6),(7),(8);

(9)endif

(10)ifRTX(s,Ω)

(11)C←Ω;

(12)endif

(13)endfor

(14)endfor

(15)returncandidate setCandRTX(s,C).

定理1 如果节点s的邻居节点集N(s)中包含目的节点d，则由算法1得到的节点s的候选节点集包含目的节点d。

证明：我们采用反证法。

假设节点s的最优候选节点集为C，{d}∩C=Ø，使得RTX(s,C)≤RTX(s,Ω),∀Ω⊂N(s)。

由1-∏j∈C(1-pj)<1-∏j∈C∪{d}(1-pj)，得S(s,C)>S(s,C∪{d})。其中，S(s,C)表示由节点s发送数据包到其候选节点集C中，并且至少有一个候选节点接收到数据包所需要的期望传输次数。另一方面，由式(9)，我们有Z(s,C∪{d})=αZ(s,C)，α=(1-p|A|)S(s,d)<1，故Z(s,C)>Z(s,C∪{d})。所以，我们可以找到一个集合C∪{d}⊂N(s)，使得RTX(s,C)>RTX(s,C∪{d})。故假设不成立，定理得证。

如何合理的应用算法1来求取网络中每一个节点的RTX指标是我们接下来考虑的问题。为此，我们提出了一个初始化算法来求取无线传感器网络中每一个节点的RTX指标。

算法2： 初始化算法

Input：network topologyG=(V,E,W),destination noded.

Output：the RTX metric and candidate set of each node

(1) LetRTX(d,d)←0,RTX(u,d)←∞,∀u≠d;

(2) LetC1←V,C2←Ø;

(3)while|C1|>0do

(4) letvbe the node inC1,which has the smallest RTX metric;

(5)C1←C1-{v};

(6)C2←C2∪{v};

(7)foreach nodeu∈C1∩N(v)do

(8) run Algorithm 1 for nodeu;

(9)endfor

(10)endwhile

算法2首先初始化目的节点d的RTX指标为0，其余节点的RTX指标为∞，并初始化两个集合C1=V，C2=Ø。然后选择集合C1中RTX指标最小的节点添加到集合C2中。假设新加入到集合C2中的节点为v，遍历C1中的节点，如果这个节点属于节点v的邻居节点集N(v)，则采用算法1计算这个节点的RTX指标。然后再次选择集合C1中RTX指标最小的节点添加到集合C2中。如此循环往复，直到集合C1为空集。

2.3 候选节点之间的协调方法

在本文所提的基于剩余能量的机会路由协议中，我们采用节点的剩余能量来对候选节点集中节点的优先级进行排序，即节点的剩余能量越大，优先级越高。由于在网络的运行过程中，节点的剩余能量是不断变化的，因此，一个候选节点集中节点的优先级排序结果也是不断更新的。为了避免数据包的冗余传输，我们采用基于应答包的协调机制来对候选节点集中的节点进行协调。关于基于应答包的协调机制的工作原理请参见文献[6]。

3 仿 真

在本文的仿真中，一个200 m×100 m的矩形区域被用来作为仿真场景，如图3所示。

图3 仿真场景

一个汇聚节点(用实心三角形表示)位于坐标(200,50)处。若干个中继节点(用实心圆点表示)随机均匀分布在这个200 m×100 m的区间内。源节点(用空心圆点表示)位于坐标(0,50)处。其它一些仿真中用到的参数在表1中给出。仿真通过将本文所提的RE-OR机会路由协议与现有的机会路由协议ExOR、EEOR和OAPF进行比较来体现本文所提的机会路由协议在网络生存周期上的优点。此外，本文还研究了节点出度W、通信距离以及中继节点个数对本文所提的RE-OR机会路由协议的影响。

表1 仿真中的一些参数

图4给出了RE-OR机会路由协议与传统的ExOR、OAPF和EEOR机会路由协议的比较结果。从图4中，我们可以看到，RE-OR机会路由协议相较于另外3种机会路由协议可以很大提升网络的生存周期。

图4 多种机会路由协议仿真的比较结果

图5～图7分别给出了节点出度W，通信距离以及中继节点个数对RE-OR机会路由协议的影响。从图5和图6中我们可以看到，选择合适的节点出度和合适的通信距离有助于增加网络的生存周期。这是由于选择较多的子节点可以使得更多的节点参与到每一轮数据的转发过程中，同时也增加了网络接收数据的开销。此外，较大的通信距离意味着比较大的传输成本，而较小的通信距离又会增加数据包传输的跳数，从而增加网络的通信成本。在图6中，中继节点的个数不同，最大网络生存周期对应的节点通信距离不同。可见，节点通信距离的选择与网络中的节点密度有很大关系。从图7中我们可以看到，网络的生存周期随着中继节点个数的增加而增加。但是，中继节点个数的增加无疑增加了网络的硬件成本。因此，选择一个合适的网络规模也是有必要的。

图5 节点出度对RE-OR协议的影响

图6 传输距离对RE-OR协议的影响

图7 中继节点个数对RE-OR协议的影响

4 结束语

本文首先提出了一个剩余传输次数指标，这个指标可以被用来选择网络中节点的候选节点集。然后，本文将剩余传输次数指标应用到以节点剩余能量为路由指标的机会路由协议RE-OR中。仿真结果表明，本文所提的基于剩余能量的机会路由协议RE-OR可以有效的延长网络的生存周期。并且，仿真结果还表明，在网络拓扑结构设计中，选择合适的节点出度，通信距离以及中继节点个数是比较重要的。