无线传感器网络PEGASIS协议的研究

李舒颜，李腊元

(武汉理工大学计算机科学与技术学院，湖北 武汉 430063)

无线传感器网络被认为是在一定空间范围内密集分布的由大量体积小、廉价、电池供电的通信器件构成的自组织系统[1－2]。通常传感器节点的电能非常有限，且电池是不可更换的，因此，传感器网络存在严重的能量约束问题。而传感器网络路由协议的首要设计目标就是要高效地利用传感器节点的能量，延长网络的生存时间。传感器节点中消耗能量的模块有传感器模块、处理器模块和无线通信模块等，其中无线通信消耗了大部分的能量[3]。研究表明，传感器节点使用无线方式传输1 bit到100 m远所消耗的能量可供处理器模块执行3 000条指令[4]。由此可见，路由协议是影响传感器网络能耗的一个非常重要的因素。此外，传感器节点采集的原始数据的数据量非常大，相邻节点的信息具有很大的冗余性，因此，应当尽可能在本地进行计算和数据融合，获得有效信息，以减少信息的发送量。

1 研究现状

按节点参与通信的方式，可以将无线传感器网络路由协议分为平面路由协议和分簇(clustering)路由协议[5]。平面路由协议的代表有 DD(directed diffusion)和 SPIN(sensor protocols for information via negotiation)等协议。由于无线传感器网络中节点数量庞大，平面路由协议会导致网络开销较大，不利于网络扩展。分簇路由协议的代表有LEACH(low－energy adaptive clustering hierarchy)和PEGASIS(power－efficient gathering in sensor information system)等协议，这种路由协议的特点是将传感节点分成不同的簇，簇内成员节点将收集的数据信息都交给簇首(cluster head)，簇首通过数据融合减少传输信息量，最后把处理后的数据传送给汇聚节点Sink(也有文献称为基站BS)。相比平面路由协议，分簇路由协议更能有效地控制拓扑，网络可扩展性更优，能量消耗更节省。

PEGASIS[6]协议是在LEACH协议基础上发展而来的基于链的路由协议。其主要思想是:为了延长网络的生命周期，节点只需要与其最近的邻居节点进行通信。节点与汇聚点间的通信过程是轮流进行的，当所有节点都与汇聚点通信后，节点间再进行新一轮回合。由于这种轮流通信机制使得能量消耗能够统一地分布到每个节点上，因此可以降低整个传输所需要消耗的能量。虽然PEGASIS减小了LEACH在簇重构过程中所产生的开销，并且通过数据融合降低了收发过程的次数，从而降低了能量的消耗，但还存在以下几个方面的问题[7]:①数据从链的远端传输到链首节点会引起过多的延迟，这对于很多对时延敏感的应用场合来说是不能接受的;②每个节点维护位置信息(相当于传统网络中的拓扑信息)而产生额外的开销;③协议所构建的接链中，远距离的节点会引起过多的数据延迟，且链首节点的唯一性使得链首会成为瓶颈;④尽管协议避免了重构簇的开销，但由于传感器节点需要知道邻居的能量状态以便传送数据，协议仍需要动态调整拓扑结构。对那些利用率高的网络而言，拓扑的调整会带来更大的开销。

正由于PEGASIS协议存在这些问题，从它被提出以来，国内外学者对此开展了相关研究。文献[8]提出了一种新的基于链状网络结构的数据路由算法EB－PEGASIS。该算法通过已成链的平均距离获得距离门限，利用距离门限避免长链形成，可以保证形成数据链上节点发送数据消耗能量基本一致，避免部分节点因消耗能量较多而过早死亡。虽然该算法可以实现网络寿命的延长，但仍然没有解决PEGASIS时延长的问题。文献[9]提出了一种被称为COSEN的路由算法，通过设置参数CL限定每条链上节点的个数，在整个观测区域构造多条短链，并在每条链上固定选取一个节点作为簇头，所有簇头再构成一条链与Sink通信，解决了PEGASIS协议中存在的时延过长的问题，但在平衡节点能量消耗、簇头节点的选择等方面仍需要进一步研究。

2 改进的PEGASIS路由协议

2.1 传感器网络模型

考虑一个由N个随机部署的传感器节点形成的网络，其应用场景为周期性的数据收集。用si表示 i个节点，相应的节点集合为 S={s1，s2，…，sn}，并基于以下假设:①所有节点完全相同，均匀分布在一个正方形区域内且静止不动，每个节点都可以与Sink直接通信;②信道是对称的，且无线电信号在各个方向上能量消耗相同;③Sink节点是固定的，在网络区域外并相距较远;④节点间的通信采用广播信道，若已知对方发射功率，节点可以根据接收信号的强度计算出发送者与自己的近似距离;⑤无线发射功率可控，即节点可以根据距离来调整发射功率的大小。

2.2 协议描述

2.2.1 节点区域划分

在系统初始化阶段，首先由Sink向观测区域的所有节点发送分区消息，将整个观察区域划分成等宽的子区间，每个节点根据自己所在的位置确定区间ID号，并向Sink发送应答信号，如图1所示。具体的区域数和每一区域的节点数由Sink根据实际情况(如节点数量，区域大小，距离远近以及节点的密度等)修改区域宽度等参数进行设置。

图1 层次区域划分和构造主链

2.2.2 节点链树构造

首先在每个区域中找出与Sink最近的节点，再在这些节点中从距离Sink最远的节点开始，采用贪婪算法构造整个网络的主链，各节点(已经在链上的节点不再参与后续的成链过程)依次找到相邻区域内距离Sink最近的节点，该节点就作为链上的下一节点形成主链，如图1所示。同时为了消除孤立节点的影响，当某一节点与区域中的任一节点的通信距离都大于与Sink的距离时，则认为该节点为孤立节点，孤立节点不参与到链中，而是直接与Sink进行通信。接着再从每个区域中距离Sink最远的节点开始，找到与其最近的节点，作为自己的父节点加入到链上(已经成为父节点的节点不再接受其他节点的请求)，然后再由新加入到链上的节点继续寻找最近的节点重复此过程，最终形成多条并行的有向链连接到主链上，这样整个网络就构成了如图2所示的有序链树。

图2 链树构造和数据传输

2.2.3 根节点(链首节点)选择

G－PEGASIS协议每一轮从主链上选择一个节点作为根节点与Sink通信。由于观测区域距离Sink较远，每轮担任根节点的节点将会消耗比普通节点多得多的能量，此外，主链上的部分节点除了接收相邻节点的数据外，还要接收与其连接的子链的数据，这样主链上的节点比子链上的节点消耗的能量多。对此，除在首轮随机选择主链上任意一个节点作为根节点以外，其后由本轮的根节点确定自己的继承人(下一轮的根节点)。具体过程是当主链上的节点向根节点传输数据时，都附上自己的剩余能量信息报告给根节点，由当前根节点指定剩余能量最多的节点担任下一轮的根节点，这样，与Sink直接通信的高负载就会平均到主链上的所有节点上。

2.2.4 数据传输

数据传输过程中，首先从每条子链的末梢节点开始并行向内传输，节点调节到最小发射功率，将自己的数据传向父节点，其父节点收到数据后与自己采集的数据进行融合处理，再发往其父节点。这样数据沿着每个区域中的子链传输，直到子链上的数据全部传送到主链节点上。而后，主链再根据PEGASIS采用的数据传输方法，先由根节点产生Token，并将Token发往主链的任意一端，由该末端节点开始向其邻居节点传输数据，同时令牌也交给邻居节点，这样数据经逐次融合后就传输到根节点上。然后根节点再将Token发往主链另外一端，重复同样的过程。最后根节点将两端传来的数据经过融合后，传输到Sink，整个过程如图2所示。

2.3 能耗分析

根据如前所述的无线传感网络特点，对PEGASlS协议和G－PEGASIS协议能量模型作如下假设:①网络能量耗费主要在数据发送、数据接收和数据融合这3个方面;②成链阶段的能量耗费相对整个数据传送阶段是很小的，可忽略不计。

而在实际中，由于接收机不接收数据时可关闭，因此接收机接收不是发给自己的数据的能量耗费可不计。

笔者采用目前比较常用的传感器节点工作能耗模型[10]，将一k b的信息传送距离d，无线通信模块的发送能耗和接收能耗分别为:

融合k b的数据信息所耗费的能量为:Eagg(k，d)=Eaggo。

式中:Eelec为传感器无线发射电路(TE)或无线接收电路(RE)发送或接收每 bit的能耗;ETx－elec(k)、ETx－amp(k，d)、ERx－elec(k)分别为发射电路、发射电路放大器和接收电路的能耗;εamp为发射放大器将每bit传送单位m2所耗的能量。

在PEGASIS协议中，n个节点的无线传感器网络沿着链传输k b的数据到链首节点所消耗的能量为:

式中:d(i，j)为链上两个节点ni到nj的通信距离。从末梢节点到链首节点数据融合消耗的能量为:

式中，Eagg为节点融合每bit数据的能耗。

在改进的PEGASIS协议，即G－PEGASIS协议中，设有m条子链，则末梢节点比PEGASIS协议多m个，这m个末梢节点可以少消耗接收和融合数据的能量为mEeIeck+mEaggk，但是主链上会有m个节点，除了接收主链上的数据外，其额外消耗接收和融合子链节点的能量也为mEeleck+mEaggk，因此，G－PEGASIS协议在所有节点数据传输到根节点阶段消耗的能量就与PEGASIS协议相等。

在G－PEGASIS协议中，每个子区域内距离Sink节点最近的节点为链首节点，其与Sink的距离为Li1，主链节点以外的节点与Sink的距离为Lij;而在PEGASIS协议中，链首节点在整个监测区域中产生，当每个区域中主链节点以外的节点被选择为链首节点时，其与Sink的距离Lij＞Li1，则消耗的能量这样在经过若干轮后，PEGASIS协议中链首节点与Sink通信所消耗的能量就会大于G－PEGASISI协议所消耗的能量。由于在G－PEGASIS协议中数据在子链上是并行传输的，这样可以有效减小数据传输延迟。此外，在PEGASIS协议中，当有节点失效时，则会重构链;而在G－PEGASISI协议中，当主链和子链上有节点失效后，整个网络不会重构链树，而是屏蔽掉失效节点，由该失效节点的两相邻节点直接进行通信。只有当各区域中离Sink最近的节点全部失效后，才会重新构造主链，且依然由各区域中与Sink距离最近的节点担任链首节点，继续与Sink通信。

3 模拟实验及分析

模拟实验采用由UC Berkley大学研发的事件驱动和面向对象的网络仿真工具NS2，场景相关参数设置如表1所示。整个区域划分为5个部分，每个部分中的节点数为20个，所有节点一旦放置就不能再移动。节点死亡只发生在能量为零时。模拟运行期间，采用网络生存周期作为算法节能的评价指标。图3为两种协议网络生存时间的比较，G－PEGASIS协议在第一个节点死亡和全部节点死亡的轮次上比PEGASIS协议有所延长。从图3可以看出，G－PEGASIS协议的网络生存时间比PEGASIS协议长13%以上。

表1 仿真参数设置

图3 两种协议网络生存时间的对比

图4为节点总的能量消耗对比，分层链树协议中节点能量消耗总和小于PEGASIS协议。

图4 节点总的能量消耗对比

4 结论

笔者在对PEGASIS协议进行深入分析的基础上，指出了其局限性，并有针对性地提出了改进后的G－PEGASIS协议。该协议通过将观测区域划分为等宽的子区间，然后根据与Sink通信距离的远近，找出每个子链中距离Sink最近的节点，建立主链，同时采取多条子链并行前向传输的方法，节省了网络的能耗，平衡了节点负载，减小了网络时延。实验结果表明，G－PEGASIS协议在生存时间、能耗均衡等方面的性能比PEGASIS协议有明显改进。

[1] AKULDIZ F，SU W，SANKARASUBRAMANIAN Y，et al.A survey of sensor networks[J].IEEE Communications Magazine，2002，40(8):102 －144.

[2] 李建中，李金宝，石胜飞.传感器网络及数据管理的概念、问题与发展[J].软件学报，2003，14(10):1717－1727.

[3] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京:清华大学出版社，2005:9－14.

[4] ESTRIN D.Wireless sensor networks tutorial part IV:sensor network protocols[M].Atlanta:Mobicom，2002:23－28.

[5] 周琴，李腊元.基于双簇头的无线传感器网络多跳路由协议[J].武汉理工大学学报:信息与管理工程版，2010，32(4):202 －205.

[6] LINDSEY S，RAGHAVENDRA C，SIVALINGAM K M.Data gathering algorithms in sensor networks using energy metrics[J].IEEE Transactions on Parallel and Distributed Systems，2002，13(9):350 －354.

[7] IBRIQ J，MAHGOUB I.Cluster － based routing in wireless sensor networks:issue and challenge[C]//Proceedings of the 2004 Symposium on Performance Evaluation of Computer Telecommunication Systems.Alifornia:[s.n.]，2004:759－766.

[8] LIU Y Y，JI H，YUE G X.An energy efficient PEGASIS based enhanced algorithm in wireless sensor networks[J].China Communications，2006，6(3):91 －97.

[9] TABASSUM N，EHSANUL Q，MAMUN K，et al.COSEN:a chain oriented sensor network for efficient data collection[M].Las Vegas:[s.n.]，2006:262 －267.

[10] WANG A，HEINZELMAN W B，SINHA A ，et al.Energy scalable protocols for battery－operated microsensor networks[J].Journal of VLSI Signal Processing，2001，29(3):223－237.