張涌逸

（太原師范學(xué)院 計算機系，山西 晉中 030619）

無線傳感器網(wǎng)絡(luò)中非線性非均勻分簇路由研究

張涌逸

（太原師范學(xué)院 計算機系，山西 晉中 030619）

文章主要為解決EEUC協(xié)議在通信量較大時，競爭區(qū)域變動幅度不能很好地使節(jié)點能量達(dá)到均衡的問題。文章提出了非線性競爭區(qū)域劃分方法，使得競爭半徑變動幅度增大，更好地適應(yīng)高數(shù)據(jù)率的需要。針對BPEC算法在產(chǎn)生簇頭過程中有的節(jié)點在剩余簇頭節(jié)點能量低于鄰居節(jié)點的平均能量的時候仍可能成為簇頭節(jié)點，這會使得有的節(jié)點很快消耗完能量，為此，文章引入了閾值，既很好地解決了簇頭節(jié)點連接的問題，也使得節(jié)點能量消耗更加均衡。

分簇路由；競爭半徑；簇頭；均衡

伴隨著無線傳感器網(wǎng)絡(luò)越來越多的應(yīng)用，人們提出了針對應(yīng)用的各種各樣的路由協(xié)定，這些協(xié)議大體上可分為3類，基于數(shù)據(jù)的路由協(xié)議、基于集群的路由協(xié)議和基于地理位置的路由協(xié)議。集群路由是一種分層路由結(jié)構(gòu)，它的主要想法是把一個個路由節(jié)點分成簇，每個簇里選出一個簇頭，一個簇內(nèi)每個節(jié)點都和簇頭通信，不同簇之間通過簇頭通信。從LEACH這個數(shù)據(jù)聚合層次路由協(xié)議提出以來，人們提出了各種各樣的分簇路由協(xié)議。文獻(xiàn)[1]中提出了非均勻的簇間路由算法，為的是解決越靠近匯聚節(jié)點需要轉(zhuǎn)發(fā)的信息越多，節(jié)點越容易擁塞、消耗的能量越多的問題。但給出的臨時簇頭競爭半徑的公式僅僅呈現(xiàn)線性的特征，變動的幅度不夠大，有的時候不能完全適應(yīng)數(shù)據(jù)通信量大時的實際需求。為了解決這個問題，我們引入了非線性情形，使得臨時簇頭競爭半徑變化的幅度加大。這更能體現(xiàn)越靠近匯聚節(jié)點簇的半徑越小，簇的成員越少的特點，路由時也更不容易出現(xiàn)擁塞。簇頭的產(chǎn)生方式也因為應(yīng)用的不同，大體上有基于剩余能量的、基于位置的、基于與鄰居距離的、基于鄰居節(jié)點的剩余能量與節(jié)點的度的等。EADEEG協(xié)議可根據(jù)剩余能量和平均剩余能量確定競爭簇頭的等待時間，減小產(chǎn)生簇頭的消息開銷，同時也能適合節(jié)點異構(gòu)的情形，但該算法會造成縫隙區(qū)域，不能保證簇頭節(jié)點的連通性。BPEC算法有效地解決EADEEG存在的縫隙區(qū)域，但低于平均剩余能量的節(jié)點會成為簇頭節(jié)點，這會造成有的節(jié)點很快地消耗完能量而失效。本文引入了閾值用來改進(jìn)BPEC算法，既解決了連接的問題也不會造成有的節(jié)點很快失效，以適應(yīng)在簇頭通信量大時，簇頭之間的能量均衡。

1 非線性非均勻競爭區(qū)域劃分方法

EEUC協(xié)議主要用來解決越靠近匯聚節(jié)點通信量越大，消耗的能量越多、擁塞的可能性也越大的問題。但EEUC協(xié)議競爭區(qū)域的劃分成線性變化，使得競爭區(qū)域間區(qū)域變化不是很大，在通信量大的時候不能完全滿足實際需要。為了進(jìn)一步擴大競爭區(qū)域的變化，我們提出了非線性的競爭區(qū)域劃分方法。

模型建立在如下的條件下；節(jié)點可根據(jù)傳輸功率來計算相互之間的距離；節(jié)點可根據(jù)距離來調(diào)整發(fā)射的功率；節(jié)點有唯一的ID號，分布區(qū)域大，分布密度大，分布均勻；基站節(jié)點位置固定，節(jié)點能量受限，基站永久提供能量；節(jié)點都是相同的，都可做簇頭節(jié)點；節(jié)點無定位功能。

取節(jié)點Ui的競爭半徑如下：

節(jié)點Ui競爭區(qū)域由線性的變?yōu)榱朔蔷€性的，以匯聚節(jié)點為中心的相鄰區(qū)域之間變化更大，更能適應(yīng)大規(guī)模大數(shù)據(jù)量通信的能量均衡和擁塞控制。

2 簇頭選舉的方法

EADEEG[4]是一個利用計時廣播方式來產(chǎn)生簇頭的方法，EADEEG每個節(jié)點保存一張鄰居表，利用鄰居表中的Ea，Eresidual，廣播競爭簇頭的等待時間如下[3-4]：

EADEEG能有效地降低開銷，保證簇頭在網(wǎng)絡(luò)中分布均勻，但會造成有的時候簇頭之間不能很好地連接。BPEC算法對EADEEG做了改進(jìn)，把等待時間分成兩種情形，一種是節(jié)點的剩余能量Er大于鄰居節(jié)點平均剩余能量Ea時，節(jié)點競爭簇頭節(jié)點進(jìn)行廣播的等待時間[2]：

另一種是節(jié)點的剩余能量Er小于等于鄰居節(jié)點平均剩余能量Ea，節(jié)點競爭簇頭節(jié)點進(jìn)行廣播的等待時間[2]：

利用參考文獻(xiàn)[2]中給出的計算公式（3），（4）可有效地解決簇頭之間不能很好連接的問題。不過，在節(jié)點的剩余能量Er小于等于鄰居節(jié)點平均剩余能量Ea情形，能做簇頭，這會造成這些節(jié)點很快消耗完能量而成為失效節(jié)點。為了解決這個問題，我們引入了剩余能量的閾值Ef。在節(jié)點的剩余能量Er小于等于鄰居節(jié)點平均剩余能量Ea情形，不是所有的節(jié)點都可成為簇頭。只有那些節(jié)點剩余能量超過閾值Ef的節(jié)點才能成為簇頭。這樣就不會出現(xiàn)節(jié)點的剩余能量Er小于等于鄰居節(jié)點平均剩余能量Ea情形那些簇頭節(jié)點很快消耗完能量，可達(dá)到能量消耗得均衡。

3 簇頭選舉算法

簇頭選舉算法。對網(wǎng)絡(luò)中的所有節(jié)點。

（1）每個節(jié)點建立一個鄰居節(jié)點列表（包括鄰居節(jié)點ID號、鄰居節(jié)點競爭范圍、鄰居節(jié)點的剩余能量），同時生成一個0，1之間隨機數(shù)u。

（2）如果u大于某個取定的值p，此節(jié)點為要競爭簇頭節(jié)點。

（3）如果節(jié)點Ui是競爭簇頭的節(jié)點就發(fā)送競爭簇頭節(jié)點消息（ID，R，RE）（R表示節(jié)點競爭范圍，由（1）可知；RE表示節(jié)點的剩余能量）。

否則就去睡眠；

（4）對每個節(jié)點Ui，如果從鄰居節(jié)點收到的信息知Uj在Ui競爭范圍內(nèi)，Ui在Uj競爭范圍內(nèi)，則把Uj添加到鄰居節(jié)點列表（利用信號強度可知相互的距離，通過相互通信可知競爭范圍）；

（5）如果Er>Ea。

由上面的（2）計算ti：

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

由上面的（3）計算ti：

否則Ui放棄競爭簇頭節(jié)點；

（7）對每個節(jié)點Ui；

while（定時器Tch沒過期）

{如果在當(dāng)前時間

4 結(jié)語

EEUC協(xié)議是為解決越靠近匯聚節(jié)點地方能量消耗越大、擁塞發(fā)生的可能性也越大的問題提出來的，但EEUC協(xié)議劃分競爭區(qū)域時候采用了線性的方式，變動的幅度不夠大，不能滿足數(shù)據(jù)流量較大的情形。在EEUC協(xié)議的基礎(chǔ)上我們采用了非線性的方法，增加了競爭區(qū)域的變動幅度，更適合數(shù)據(jù)流量較大的情形。另外，在選取簇頭的時候，EADEEG協(xié)議能有效地降低開銷，保證簇頭在網(wǎng)絡(luò)中分布均勻，但在某些情形簇頭之間不能很好地連接，BPEC算法的提出，能很好地解決簇頭之間的連接問題，可是，在節(jié)點能量低于鄰居節(jié)點的平均剩余能量的情況下，仍可能成為簇頭節(jié)點，這會使得有些節(jié)點很快消耗完能量。為了解決此問題，文章引入了閾值，也就是只有節(jié)點的能量高于某個閾值的時候才能擔(dān)任簇頭節(jié)點，有效地避免了節(jié)點較早失效的問題，達(dá)到能量消耗的均衡。

[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：無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法[J].計算機研究與發(fā)展，2009（5）：723-730.

[3]蔣暢江，向敏.無線傳感器網(wǎng)絡(luò)：路由協(xié)議與數(shù)據(jù)管理[M].北京：人民郵電出版社，2013.

[4]劉明，曹建農(nóng)，陳貴海，等. EADEEG：能量感知的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議[J].軟件學(xué)報，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— ），男，山西河曲，碩士，副教授；研究方向：網(wǎng)絡(luò)路由，無線傳感器網(wǎng)絡(luò)。