无线传感器网络中非线性非均匀分簇路由研究

张涌逸

（太原师范学院 计算机系，山西 晋中 030619）

无线传感器网络中非线性非均匀分簇路由研究

张涌逸

（太原师范学院 计算机系，山西 晋中 030619）

文章主要为解决EEUC协议在通信量较大时，竞争区域变动幅度不能很好地使节点能量达到均衡的问题。文章提出了非线性竞争区域划分方法，使得竞争半径变动幅度增大，更好地适应高数据率的需要。针对BPEC算法在产生簇头过程中有的节点在剩余簇头节点能量低于邻居节点的平均能量的时候仍可能成为簇头节点，这会使得有的节点很快消耗完能量，为此，文章引入了阈值，既很好地解决了簇头节点连接的问题，也使得节点能量消耗更加均衡。

分簇路由；竞争半径；簇头；均衡

伴随着无线传感器网络越来越多的应用，人们提出了针对应用的各种各样的路由协定，这些协议大体上可分为3类，基于数据的路由协议、基于集群的路由协议和基于地理位置的路由协议。集群路由是一种分层路由结构，它的主要想法是把一个个路由节点分成簇，每个簇里选出一个簇头，一个簇内每个节点都和簇头通信，不同簇之间通过簇头通信。从LEACH这个数据聚合层次路由协议提出以来，人们提出了各种各样的分簇路由协议。文献[1]中提出了非均匀的簇间路由算法，为的是解决越靠近汇聚节点需要转发的信息越多，节点越容易拥塞、消耗的能量越多的问题。但给出的临时簇头竞争半径的公式仅仅呈现线性的特征，变动的幅度不够大，有的时候不能完全适应数据通信量大时的实际需求。为了解决这个问题，我们引入了非线性情形，使得临时簇头竞争半径变化的幅度加大。这更能体现越靠近汇聚节点簇的半径越小，簇的成员越少的特点，路由时也更不容易出现拥塞。簇头的产生方式也因为应用的不同，大体上有基于剩余能量的、基于位置的、基于与邻居距离的、基于邻居节点的剩余能量与节点的度的等。EADEEG协议可根据剩余能量和平均剩余能量确定竞争簇头的等待时间，减小产生簇头的消息开销，同时也能适合节点异构的情形，但该算法会造成缝隙区域，不能保证簇头节点的连通性。BPEC算法有效地解决EADEEG存在的缝隙区域，但低于平均剩余能量的节点会成为簇头节点，这会造成有的节点很快地消耗完能量而失效。本文引入了阈值用来改进BPEC算法，既解决了连接的问题也不会造成有的节点很快失效，以适应在簇头通信量大时，簇头之间的能量均衡。

1 非线性非均匀竞争区域划分方法

EEUC协议主要用来解决越靠近汇聚节点通信量越大，消耗的能量越多、拥塞的可能性也越大的问题。但EEUC协议竞争区域的划分成线性变化，使得竞争区域间区域变化不是很大，在通信量大的时候不能完全满足实际需要。为了进一步扩大竞争区域的变化，我们提出了非线性的竞争区域划分方法。

模型建立在如下的条件下；节点可根据传输功率来计算相互之间的距离；节点可根据距离来调整发射的功率；节点有唯一的ID号，分布区域大，分布密度大，分布均匀；基站节点位置固定，节点能量受限，基站永久提供能量；节点都是相同的，都可做簇头节点；节点无定位功能。

取节点Ui的竞争半径如下：

节点Ui竞争区域由线性的变为了非线性的，以汇聚节点为中心的相邻区域之间变化更大，更能适应大规模大数据量通信的能量均衡和拥塞控制。

2 簇头选举的方法

EADEEG[4]是一个利用计时广播方式来产生簇头的方法，EADEEG每个节点保存一张邻居表，利用邻居表中的Ea，Eresidual，广播竞争簇头的等待时间如下[3-4]：

EADEEG能有效地降低开销，保证簇头在网络中分布均匀，但会造成有的时候簇头之间不能很好地连接。BPEC算法对EADEEG做了改进，把等待时间分成两种情形，一种是节点的剩余能量Er大于邻居节点平均剩余能量Ea时，节点竞争簇头节点进行广播的等待时间[2]：

另一种是节点的剩余能量Er小于等于邻居节点平均剩余能量Ea，节点竞争簇头节点进行广播的等待时间[2]：

利用参考文献[2]中给出的计算公式（3），（4）可有效地解决簇头之间不能很好连接的问题。不过，在节点的剩余能量Er小于等于邻居节点平均剩余能量Ea情形，能做簇头，这会造成这些节点很快消耗完能量而成为失效节点。为了解决这个问题，我们引入了剩余能量的阈值Ef。在节点的剩余能量Er小于等于邻居节点平均剩余能量Ea情形，不是所有的节点都可成为簇头。只有那些节点剩余能量超过阈值Ef的节点才能成为簇头。这样就不会出现节点的剩余能量Er小于等于邻居节点平均剩余能量Ea情形那些簇头节点很快消耗完能量，可达到能量消耗得均衡。

3 簇头选举算法

簇头选举算法。对网络中的所有节点。

（1）每个节点建立一个邻居节点列表（包括邻居节点ID号、邻居节点竞争范围、邻居节点的剩余能量），同时生成一个0，1之间随机数u。

（2）如果u大于某个取定的值p，此节点为要竞争簇头节点。

（3）如果节点Ui是竞争簇头的节点就发送竞争簇头节点消息（ID，R，RE）（R表示节点竞争范围，由（1）可知；RE表示节点的剩余能量）。

否则就去睡眠；

（4）对每个节点Ui，如果从邻居节点收到的信息知Uj在Ui竞争范围内，Ui在Uj竞争范围内，则把Uj添加到邻居节点列表（利用信号强度可知相互的距离，通过相互通信可知竞争范围）；

（5）如果Er>Ea。

由上面的（2）计算ti：

（6）否则如果p≤Er，且Ef≤Er；

由上面的（3）计算ti：

否则Ui放弃竞争簇头节点；

（7）对每个节点Ui；

while（定时器Tch没过期）

{如果在当前时间

4 结语

EEUC协议是为解决越靠近汇聚节点地方能量消耗越大、拥塞发生的可能性也越大的问题提出来的，但EEUC协议划分竞争区域时候采用了线性的方式，变动的幅度不够大，不能满足数据流量较大的情形。在EEUC协议的基础上我们采用了非线性的方法，增加了竞争区域的变动幅度，更适合数据流量较大的情形。另外，在选取簇头的时候，EADEEG协议能有效地降低开销，保证簇头在网络中分布均匀，但在某些情形簇头之间不能很好地连接，BPEC算法的提出，能很好地解决簇头之间的连接问题，可是，在节点能量低于邻居节点的平均剩余能量的情况下，仍可能成为簇头节点，这会使得有些节点很快消耗完能量。为了解决此问题，文章引入了阈值，也就是只有节点的能量高于某个阈值的时候才能担任簇头节点，有效地避免了节点较早失效的问题，达到能量消耗的均衡。

[1]LI C, YE M, CHEN G, et al.An energy-ef fi cient unequal clustering mechanism for wireless sensor networks[C].Washington DC：IEEE International Conference on Mobile Ad Hoc & Sensor Systems Conference, 2005：559-604.

[2]周新莲，吴敏，徐建波. BPEC：无线传感器网络中一种能量感知的分布式分簇算法[J].计算机研究与发展，2009（5）：723-730.

[3]蒋畅江，向敏.无线传感器网络：路由协议与数据管理[M].北京：人民邮电出版社，2013.

[4]刘明，曹建农，陈贵海，等. EADEEG：能量感知的无线传感器网络数据收集协议[J].软件学报，2007（5）：1092-1109.

Research on nonlinear nonuniform clustering routing in wireless sensor networks

Zhang Yongyi
（Computer Science Department of Taiyuan Normal University, Jinzhong 030619, China）

This paper mainly deals with the problem that the energy of the node can not be well balanced by range of fluctuation in competition in the EEUC protocol when the traf fi c volume is large. In this paper, a nonlinear competitive region partitioning method is proposed, which makes the competition radius amplitude of fl uctuation increase, so as to better adapts to the high data rate needs. For the BPEC algorithm, some nodes are still possible to be cluster node when the energy of residual cluster head node is lower than the average energy of neighbor nodes. This will make some nodes drain the energy quickly, therefore, the threshold value is introduced in this paper, which better solves the problem of cluster node connection, and also makes the node energy consumption more balanced.

clustering routing; competition radius; cluster head; balance

张涌逸（1968— ），男，山西河曲，硕士，副教授；研究方向：网络路由，无线传感器网络。