改进基站选择Sink的节能无线传感器网络

摘 要：本文综合多个方面考虑网络体系结构的优化，在基于LEACH和PEGASIS的核心思想上，改进了HEARA协议。经分析改进协议充分利用了网络的特点，进一步延长了网络的生命周期。

关键词：网络体系结构；HEARA；协议；生命周期

中图分类号：TP393

无线传感器网络（Wireless sensor network）[1]中传感器节点能量有限，一条好的网络体系结构可以大大延长网络的生命周期。HEARA协议[2]延长了网络的生命周期，但却不是最大化。LEACH协议[3]和PEGASIS协议[4]是当前最典型的算法。

1 算法改进

1.1 改进算法的体系结构

改进算法采用了几条同等角的边和同圆心的环将网络分为多个扇形结构的小区域，网络体系结构如图1所示。

图1 改进算法的体系结构

在每个小区域内，基站根据节点所发送的信息，判断、选择能量最大的一个作为簇头，簇头从环的内层到外层用A（i，1），A（i，2），…，A（i，j），…，A（i，k）表示，其中A（i，j）中的i和j分别代表第i条边和第j条环。簇头一方面承担着簇内PEGASIS链数据的融合、汇聚的工作；另一方面，将处理后的数据信息传递给前面的簇头或者直接发送给基站。

1.2 链路选择

在文献[5]中，假设节点i的当前能量和负载分别为Ei、Li，则定义它此时的代价Costi为：

Costi=Ei/Li （1）

在构造PEGASIS链的时候，节点从邻居节点中选择代价值最小的作为它的下一跳。因此，整条链路的代价可达到最小值，其代价为：

（2）

其中，N代表该链中节点的个数，Cost为整条链路的代价。

2 改进算法流程

本算法的每个回合分为三个阶段：路由建立、数据传输和路由维护。下面分别介绍这三个阶段的过程。

2.1 路由建立阶段

（1）所有节点将自己当前的能量值和位置信息组成信息包，发送给基站；（2）基站接收到信息后，选择其中能量较大的几个作为簇头，并将这个信息发送给所有节点；（3）每个簇头接到信息后，再向每个节点发送组成簇内节点的信息；（4）节点成功收到信息后，根据节点与簇头距离的不同，确定它应该属于哪个簇头，且保存它的簇头的信息；（5）之后，节点给它的簇头发送一信息，表明它已经属于这个簇头；（6）簇头A（i，j）保存A（i，j+1）和A（i，j-1）信息，分别用于给簇头A（i，j+1）分配时间片和发送数据给簇头A（i，j-1）；（7）在每个簇内，最远的节点通过查询它的邻居节点表，找到与Cost值最小的节点作为链它的下一跳；（8）如此重复步骤（7），直到找一条从最远节点到簇头的链路为止；（9）簇头A（i，j）为簇内节点和簇头A（i，j+1）设定TDMA时间片。

2.2 数据传输阶段

（1）节点在它的簇头所分配的时间片内监测、收集数据，并发送给链中它的下一跳；（2）同样，在TDMA分配的时间内下一跳节点接收到数据，将自己的数据与收到的数据进行融合处理，并发送给它的下一跳；（3）重复步骤（2），直到数据传到它簇头A（i，j）；（4）簇头A（i，j）把数据处理、融合后，在簇头A（i，j-1）的TDMA所分配的时间片内将数据发送给簇头A（i，j-1）；（5）如此重复步骤（4），直到数据传到直接传递到基站。

2.3 路由维护阶段

本算法为不同类型的节点设置不同的门阀值。为簇头设置的门阀值为当前能量的20%，而一般的节点的门阀值设为当前能量的10%。

当簇头A（i，j）的能量等于或者低于门阀值时，它分别将此消息告诉给基站、簇头A（i，j-1）、簇头A（i，j+1）、簇内节点。当基站收到更换簇头的消息后，立刻再根据节点的能量值选择能量最大的作为簇头，并将此消息告诉给其簇内节点。簇内节点收到簇头选好的消息后，重新生成PEGASIS链。

当某节点的能量等于或者低于门阀值时，它只将该信息沿着链传送给它的簇头，簇头得知簇内节点快消耗完能量的消息后，发送一重新建立链的消息给簇内节点，节点收到信息后，立刻重新建立一条从最远的节点到簇头的一条链路。

3 改进算法性能分析

图2 改进算法性能分析

在a图中，设两算法的在该区域内的链构造相同，N0―N8为改进算法在这个区域内的节点，N0是这个区域内的簇头，而HEARA算法以N0为簇头的簇区域为虚线圆部分，包括节点N0―N10。假设链上邻居节点之间数据传输需要的时间为1s，那么在改进算法中数据从N8传到N0需要3s，而由于原算法中节点N8必须等候N10的数据发送过来，再经融合后才能通过链上数据传输最终发送N0，因此N8的数据最终到达簇头时延为5s。因此，改进算法比原算法减少了数据传输的平均时延。

b图和c图分别为HEARA算法与改进算法在同一区域内的数据传输路径图。由于HEARA算法中节点选择下一跳的标准为所有邻居节点中与它距离最近的那一个，改进算法根据邻居节点中能量较大而负载较小的一个作为它的下一跳。因此，b图中N7选择了N6，N5选择了N4作为它们的下一跳节点，而在c图中N7却选择了Cost较小的N2作为它的下一跳，N5直接选择了能量较大的簇头N0作为它的下一跳。通过这种选择较小的Cost值较小的节点作为下一跳来构造链，不仅优化了链，节约了节点的资源，而且延长了网络的生命周期。

4 小结

针对HEARA算法的不足，综合利用节点的能量、负载以及分区原理来对算法进行改进。通过分析改进算法一定程度上能够延长网络的生命周期。

参考文献：

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

[2]邓亚平，陈莉.基站选择Sink的无线传感器网络路由协议[C].计算机应用.2009，12，47-49.

[3]Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]. Proc of the 33rd Annual Hawaii Int’1 Conf on System Sciences， 2000， 3003-3014.

[4]Lindsey S， Raghavendra C S. PEGASIS： Power efficient gathering in sensor information systems[C]. Proceedings of IEEE Aerospace Conference. 2002， 3： 1125-1130.

[5]Chengjie Wu， Ruixi Yuan， Hongchao Zhou. A novel load balanced and lifetime maximization routing protocol in wireless sensor networks[C]. IEEE 67th vehicular technology conference.2008，3：113-117.

作者简介：陈莉（1984.4-），女，四川省都江堰市人，计算机教研室助教，硕士学位，研究方向：计算机网络与通信。

作者单位：四川外国语大学成都学院，成都 611844