一种基于交错分链结构的路由协议

苏鹏举，徐玉斌

(太原科技大学计算机科学与技术学院，太原 030024)

无线传感器网络综合了微电子技术、网络通信技术和传感器技术等技术，应用于军事、医疗、交通、工业和民用等领域，具有巨大的应用价值，引起了世界各国的高度重视[1-2]。它是由具有感知数据、无线通信能力和信息处理能力的传感器节点组成。网络中的节点之间以无中心的无线多跳方式连接，能够协同工作，可以实时监测和采集各种环境和监测对象的相关信息。

无线传感器网络中的节点通常工作在野外较为恶劣的环境之中，能量是一般由电池来供应。而电池的能量有限，并且难以在工作的时候更换，所以有限的节点能量决定了网络的生存时间[3]。无线传感器网络的这个特点决定了传统的路由协议在网络中无法直接应用，需要设计新的适用于无线传感器网络的节能路由协议。

LEACH[4]协议和 PEGASIS[5]协议是典型的无线传感器网络路由协议，本文在此基础上，以均衡节点能耗和延长网络生存周期为目标，针对其不足进行的改进，提出了基于交错分链结构的路由协议，改进后的协议在节能方面具有了更好的性能。

1 LEACH协议和PEGASIS协议

LEACH协议和PEGASIS协议是无线传感器网络路由协议中典型的分层路由协议。其中，LEACH协议是最早的分层路由协议。LEACH协议随机的簇头选举机制，使得整个传感器网络的能量负载平均分配到每个节点上，延长了网络生存周期。LEACH协议与一般的平面多跳路由协议以及静态分层算法相比，生命周期延长了15%.其选择簇头的公式如下:

其中，p是网络中簇头数占所有节点数的百分比，也是节点可能担当簇头的概率值;r是当前运行的轮数;G是在最近的1/p轮中还未曾担任过簇头的节点集合。在簇建立的时候，每个节点会产生一个界于0和1之间的随机数字，与阈值T(n)进行对比，如果小于该阈值，此节点就被选为簇头，反之则不然。

LEACH协议中的簇头每次都是随机产生的，所以簇头的位置会出现分配不均匀，对节约节点能量不利。另外，每个簇头直接与基站节点通讯，这会导致距离基站远的节点能量提前耗尽，因而该协议均衡节点能耗的性能较差。

PEGASIS协议是对LEACH协议的改进，核心思想是:采用贪婪算法，每个节点只和它的最近邻居节点通信，节点轮流担任Leader节点，负责与基站通信，当所有节点都担任过Leader节点以后，再进行新一轮的通信。PEGASIS协议的这种轮流通信机制使得能量消耗统一分配到每个节点上，从而降低了整个传输过程的能量消耗。与LEACH协议相比，PEGASIS协议提高了近两倍的生命周期。但是PEGASIS协议也有不足:网络中每个节点都能直与基站通信，从而导致远端节点在担任链的首节点期间要消耗相对较多的能量;PEGASIS协议节点具有相同的初始能量，因此可能在同一时间全部死亡;PEGASIS协议所构造的链中，运用贪婪法经常会引起长链，这也会导致长链两端的节点能量消耗相对较大。

2 其他相关改进算法

由于LEACH协议和PEGASIS协议存在的不足，国内外学者对其进行了改进。LEACH协议的改进算法有LEACH-C[6]协议等。PEGASIS协议的改进算法有EEPB[7]算法和基于遗传算法的无线传感网PEGASIS算法的改进[8]等。

LEACH-C协议对分簇的算法进行了改进，不再随机选择簇头。它是一种集中式的分簇路由协议，在其每个周期的开始阶段，所有节点把自己的位置信息和剩余能量值发往基站。基站在收到这些信息后，首先计算所有节点的平均能量值，把能量不低于平均能量值的节点作为候选节点。这种方式能够减少选举簇头时因通信而消耗的能量，从而有更多的剩余能量用于传输数据。

EEPB协议通过引进距离门限避免相邻节点长链的产生。在选举Leader节点时候，考虑了节点的剩余能量和节点到基站的距离值两个参数。基于遗传算法的无线传感网PEGASIS算法的改进在其链形成阶段采用遗传算法，减少了传输距离。此算法鉴于发送数据时消耗的能量与传输距离的平方成正比，尽可能形成一条距离的平方和最短的链，并根据节点的剩余能量进行簇头选择。这两种协议平衡了各节点的能耗，具有比PEGASIS协议更好的节能性。

3 交错分链结构的路由协议

基于LEACH协议和PEGASIS协议的分析，本文提出了一种改进的路由协议:交错分链结构的路由协议。

网络假设:

(1)节点的发射功率可以动态调节，从而节省能量;

(2)网络中的节点是同构的，也就是具有相同的通讯能力以及数据处理能力，都有可能成Leader节点;

(3)所有节点都是静止的，符合大多数的应用环境;

(4)所有节点都有一跳和基站通信的能力。

(5)每个节点在网络中有唯一的ID号，并且能够感知自己的坐标值。

3.1 链的划分

网络节点随机分布以后，建立一个包含所有节点的网络直角坐标系。每个传感器节点通过自己的坐标值计算自己的横链标识号和纵链标识号，计算公式如下:

Cluster_id_horizontal=ceil(y*p));

Cluster_id_row=ceil(x*p));

其中，Cluster_id_horizontal代表横链的标识号，Cluster_id_row表示纵链的标识号。ceil表示将某个值向上取整数值。如:ceil(1.1)=2.p代表链数占节点总数的百分比，x和y代表节点的坐标值。

3.2 Leader的选举

整个网路中存在唯一的Leader，选举的策略是剩余能量最大的节点作为Leader.首轮Leader随机选举，因为在第一轮的时候节点的能量都大致相同。由基站向整个网络广播Leader的信息。此后，由链端节点开始把自己剩余能量的消息告诉下一跳节点。这个过程采用信息捎带技术，与采集的数据在同一数据包内。下一跳传感器节点收到该数据包以后，提取剩余能量部分的信息，与自己的剩余能量对比，把较大剩余能量的节点信息传送给自己的下一跳节点。依此类推，最后把剩余能量最大的节点信息传送给基站。

基站将采集的数据进行处理，并提取网络中剩余能量最大的节点信息，该节点将作为下一轮的Leader。然后，基站向整个网络广播该节点信息，开始新一轮的数据采集。

本文并没有引进距离作为选举leader的参数。因为引进距离参数以后，只会提前消耗距离基站较近节点的能量，实际意义不大，反而会增加算法复杂度。

3.3 节点成链

在第一轮成链的时候，需要先建立路由表。此时采用基站统一管理的方式:按照节点ID的大小顺序，节点依次把自己的相关信息传送给基站。该信息包括:节点的ID，坐标值，横链和纵链的标识号。基站收到所有节点的数据信息后，进行处理，得出每个节点的路由信息。每个路由信息包含横链上的邻居节点信息和纵链上的邻居节点信息。然后，基站按照节点ID的大小顺序，依次把路由信息发送给相应节点，收到路由信息的节点建立路由表，并保存路由信息。

在基站广播Leader节点的信息以后，每个节点查看自己的纵链标识号，查看是否和Leader在同一纵链内，如果纵链标识号不同，只进行横链方向的数据传输。如果和Leader节点的纵链标识号相同，就要进行纵链方向的数据传送，此外还要查看横链上的邻居节点是否和自己在同一纵链内。如果横链上的邻居节点和自己在同一纵链上，只进行纵链方向的传输，否则，还要接收来自该相邻节点的数据信息。

在每轮开始的时候，每个节点根据Leader节点的信息分析自己数据的传送方向以及应该接收的数据包的数量。通过数据传输的方向以及应该接收的数据包数量，每个节点就可以计算出本轮的能量消耗。如果自己的剩余能量不足以承受，就广播消息告知邻居节点刷新相关的路由表，该节点就默认为死亡。广播消息的半径是邻居节点中最远节点的距离值。

根据路由表构链的时候，如果发现某个节点的下一跳节点跳过了本轮Leader的纵链区域，该节点就要在Leader所在纵链上寻找一个距离最近的节点，并把采集的数据传送给这个最近节点。

通过以上两种方式，可以保证每次通信的过程中都不会出现盲点，发生断链现象，同时避免了拓扑重构。

在链结构形成以后，整个网络的拓扑结构如下图1所示:图中黑色实线代表网络中节点之间形成的横链，虚线线表示和Leader在同一纵链内的节点形成的纵链，点线表示横链和纵链之间的连接线，圈中带*的节点表示Leader节点。

图1 拓扑结构Fig.1 The structure of topology

3.4 网络通信阶段

整个网络拓扑结构建立完成以后，节点根据自己的路由表可以查出是否是链端节点。链端节点首先开始传送数据。节点在接收到来自邻居节点的数据信息以后，查看是否所有数据都已经接收完毕。当接收完所有的信息以后，把相关的数据信息进行数据融合，并传给下一跳节点。最终把数据传给Leader，再由Leader将数据传给基站。

4 仿真过程及结果

在MATLAB上进行仿真实验，采用的能量模型如下:

其中，Esend为发送每位数据所消耗的能量，k为发送数据的长度，d是发送数据的距离，Efs表示传送数据时能量消耗的系数，与数据长度和距离平方值相关。

当接收数据时，模型如下:

其中EDA为数据融合时的能量消耗参数。ERX表示接收每位数据的能量消耗。

仿真环境:将100个节点随机分布在整个正方区域内，正方形区域的半径为100 m，基站的位置坐标是(50，300)，远离整个网络，节点初始能量为0.25 J，数据包大小为2000 bits.表1是其他参数值的说明。

表1 仿真参数表Tab.1 The parameters of simulation

4.1 首节点死亡

以第一个节点死亡的时间作为网络的生命周期[9]，分别对三种路由协议进行了仿真实验，得出三种路由协议的实验结果，参数对比如图2.

图2 能耗对比图Fig.2 The comparison of energy consumption

从图中的可以看出:LEACH协议的网络寿命为180轮，PEGASIS协议的网络寿命为330轮，而交错分链结构路由协议的网络寿命为800轮。因此，交错分链结构路由协议大大提高了网络的寿命。

4.2 剩余总能量和运行轮数的关系

剩余总能量和运行轮数的关系如图3所示。

图3 剩余能量与运行轮数的关系Fig.3 The relation of residual energy and rounds

随着数据的传输轮数的增多，每个节点的剩余能量不断减少，总的剩余能量也随之减少。LEACH协议中的节点总剩余能量在340轮左右消耗殆尽，此时交错分链结构路由协议的总能量消耗了大约40%.PEGASIS协议的能量消耗比LEACH要好，但是差于分链结构路由协议，在不到760轮的时候全部死亡，交错分链结构路由协议全部死亡大约在850轮。

4.3 分链数目的影响

本文把整个网络分为五个横链，是实验后得出的结果。本文分别对 2、4、5、7、9五种不同的链数进行了仿真实验，得出图4的对比图。

图4 不同分链数量的对比Fig.4 The comparison of different partition － chain amount

由图4可以看出:当分为五个链的时候，首节点的死亡时间达到最大运行轮数，随着链数值的增大或减小，这个数值都会逐渐减小。所以，当链数值为5的时候，本协议的性能最好。

在实验的结果中还得出表2的数据，表中p表示链数与网络节点总数的比值。例如:节点总数为100，当p=0.02，就表示分为两个链。通过表2可知当p=0.05的时候，无论是是首节点死亡时间，还是节点全部死亡的时间，网络都能达到最好的性能。

表2 不同分链数的性能对比Tab.2 The performances of different amount of chain

5 结束语

交错分链结构路由协议改进了LEACH协议的簇分配不均等问题，也改进了PEGASIS协议中存在的长链现象。交错分链结构路由协议拓扑结构形成以后，就不会改变，不像LEACH协议，需要不断的改变拓扑结构。PEGASIS协议在有节点出现死亡的时候，需要重构网络，这样在网络后期有大量节点死亡的时候，将会不断地进行拓扑重构。交错分链结构路由协议只需要刷新相关节点的路由表，跳过死亡节点，因此节省了网络拓扑重构消耗的能量。另外，本协议的Leader选举策略与PEGASIS协议相比，在均衡网络中节点能耗的方面性能更好。

总之，交错分链结构的路由协议与LEACH协议和PEGASIS协议相比，在能量负载平衡和网络的生命周期方面都有很大的提高。

[1]REN FENG-YUAN，HUANG HAINING，LIN HUANG.Wireless Sensor Network[J].Journal of Software，2003，4(7):1282-1291.

[2]LAN F AKYILDIZ，SU WEILIAN，YOGESH SANKARASUBRAMANIAM，et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[3]张治中，曾建潮.基于PSO的无线传感器网络自组织成簇算法[J].太原科技大学学报，2009，30(6):484-489.

[4]宋文，王兵，周应兵.无线传感器网络技术与应用[M].北京:电子工业出版社，2007:2-3.

[5]WENDI RABINER HEINZELMAN，ANANTHA CHANDRAKASAN，HARI BALAKRISHNAN.Energy-Efficient Communication Protoclo for Wireless Microsensor Networks[C]//Proceedings of the 33rdHawaii International Conference on System Sciences，USA，Hawaii，2000.

[6]LINDSEY S，RAGHAVENDRA C.PEGASIS:Power-efficient gathering in sensor information[C]//IEEE Aerospace Conference Proceedings，SanFrancisco:IEEE Computer Society，2002.1125-1130.

[7]HEINZELMAN W，CHANDRAKASAN A，BALAKRISNAN H.An applicationspecific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications，2002，1(4):660-670.

[8]余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法[J].电子学报，2008，36(7):1309-1313

[9]胡森来，张昱，金心宇，等.基于遗传算法的无线传感网的PEGASIS协议的改进[J].江南大学学报(自然科学版)，2008，7(4):420-424.

[10]田莹，王莹，张淑芳.高效节能的链式分层无线传感器网络路由协议[J].计算机工程与应用，2007，43(35):22-26.