無線傳感器網絡中非線性非均勻分簇路由研究

張涌逸

（太原師范學院 計算機系，山西 晉中 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— ），男，山西河曲，碩士，副教授；研究方向：網絡路由，無線傳感器網絡。