基于多級異構網絡的無線傳感器網絡高效分簇路由算法

李新路 張貫虹

（合肥學院，安徽 合肥 230601）

基于多級異構網絡的無線傳感器網絡高效分簇路由算法

李新路 張貫虹

（合肥學院，安徽 合肥 230601）

在較大規模的無線傳感器網絡周期性數據采集應用中，經常會出現異構網絡，LEACH等協議沒有考慮節點的異質性。提出一種基于多級異構網絡的高效路由分簇協議，考慮了節點的異質性，為不同類型節點設置不同簇頭選舉概率及閾值函數，優化簇頭選舉策略，較高初始能量和剩余能量的節點比低能量節點擁有更多的機會成為簇頭節點。實驗結果表明，能夠高效地利用傳感器網絡采集數據，網絡負載總體均衡，并延長網絡生存周期。

無線傳感器網絡；異構網絡；能量高效

無線傳感器網絡（Wireless Sensor Networks，WSNs）由許多小型的，資源有限的傳感器節點以及基站組成的自組織、分布式網絡［1］。隨著傳感器系統，數據處理及無線通信的發展，無線傳感器網絡技術被廣泛的應用于各類應用，如環境監測、軍事、化工檢測、醫療服務等行業［2］。由于傳感器節點的初始能量、帶寬、計算能力的限制，廣泛應用于有線網絡或Ad Hoc網絡中的協議并不適用與WSNs。因而，設計出能量高效的路由協議，從而延長網絡生命周期，成為WSNs研究的一個熱點問題［1］［3］。

1 相關工作

在WSNs路由協議的設計中，分簇路由協議是較為經典、高效的路由協議，它將網絡中的節點劃分成簇頭節點和成員節點兩類，首先使用特定的策略選舉簇頭，再根據距離等權函數形成簇，簇頭負責管理簇內成員節點，執行數據聚合函數，并傳輸數據到基站。LEACH（Low-Energy Adaptive Clustering Hierarchy）［4］是WSNs中最早提出的分簇路由協議，它是分簇路由協議的基礎。其基本思想是，通過等概率隨機周期性的選擇簇頭，再利用節點與簇頭之間的距離形成簇，將整個網絡的能耗均勻地分配到每一節點，從而達到降低能耗總量，延長網絡生命周期的目的。但是LEACH沒有考慮到節點的剩余能量問題，加速熱點問題（hot spot problem）的形成。文獻［5］提出一種DCHS路由協議，DCHS改進了簇頭選舉過程中的閾值函數，考慮了節點的剩余能量因素，使得節點能耗更加均勻，避免節點過早“死亡”。

HEED［6］是一種混合式能量高效的分布式分簇協議，它根據節點的剩余能量來選擇候選簇頭，并使用節點的度或鄰接節點距離作為內部通信代價，以此來競爭產生最終簇頭。實驗證明，在一定的節點密度和簇內簇間通信半徑下，HEED可以確定一個連通的分簇網絡，延長網絡生命周期，并使得網絡更具有擴展性。但是，HEED需要有限次迭代來選擇簇頭，其簇頭選舉開銷比LEACH大了許多，在采用單跳模式下，其性能不如LEACH。

EECS［7］適用于周期性的數據收集應用，它在簇頭選舉階段選取部分節點參加競爭，采用無迭代過程的局部通信方式，選取剩余能量較多的節點擔任簇頭，進一步，在簇的形成階段使用了一種簇頭負載均衡的方法。EECS協議控制消息開銷小，形成的簇在空間上分布近似均勻，網絡能量利用率高。

這些基于LEACH的路由協議大都假定網絡節點是同質的，即節點具有相同的初始能量和計算能力，然而在一些應用中，如在現有網絡中增加部分新節點，網絡中會存在大量異質節點。Mhatre等人在文獻［8］［9］中同時考量能耗成本及硬件成本作為整個網絡成本，較早地分析比較了WSNs中同質網絡和異構網絡的路由協議。UCS協議［10］針對異構網絡，提出了非均勻分簇的路由策略，UCS假定所有高初始能量的節點位置已知，并指定其為簇頭節點，簇間通信采用多跳方式。為均衡能量負載，UCS利用文獻［8］提出的能耗模型，使網絡中的分簇大小不均勻分布，即距離基站較近的簇成員較少，從而達到整個網絡中簇頭能耗均勻的目的。SEP［11］協議考慮網絡中存在兩種初始能量不同的節點，通過在簇頭選舉概率和閾值函數中引入初始能量，使得具有較高能量的節點具有較大概率成為簇頭，延長了傳感器網絡的穩定周期①穩定周期指從網絡開始運行直到第一個傳感器節點失效的時間間隔。在一些應用中，當一個傳感器節點失效后，網絡會變的很不穩定。。

本文提出一種基于三級異構網絡的分簇路由協議。LEACH及類LEACH分簇協議基于同構網絡，在處理異構網絡時沒有考慮節點的異質性，從而使得節點的能耗分布不均勻。而UCS協議需要提前獲取異質節點的位置，并且要求它們位置分布均勻，因而具有很大的局限性，不能滿足無線傳感器網絡的拓撲變化。本文的協議區別于這兩類協議，在考慮網絡擴展性和穩定性的基礎上，使得節點能量負載均衡，從而延長網絡的生命周期。

2 問題描述和能量模型

2.1 問題描述

本文提出的協議基于周期性數據收集應用，如環境監測等，我們假定：

（1）節點隨機均勻地分布在監測區域，位置信息未知，基站位置固定；

（2）節點能量有限，網絡中存在異質節點，基站能量不受限制；

（3）節點具有相似的處理及通信能力，可以擔任簇頭或普通節點；

（4）節點通信功率可控，可以根據距離來調節發射功率的大小，并可以根據接收信號的強度來計算節點之間的距離。

本文研究的無線傳感器網絡模型中有n個傳感器節點，一個基站。傳感器節點初始能量不均勻。同時，我們假定在網絡中有三種不同類型的節點：普通節點（normal nodes），中級節點（moderate nodes），高級節點（advance nodes）。

2.2 能量模型

本文采取與文獻［12］相同的能量模型。節點傳輸l比特的消息到距離為d的位置，消耗的能量由發射電路損耗和功率放大損耗兩部分組成，即

同時，為了接收比特的消息，需消耗能量為：

其中，Eelec表示發射電路損耗的能量。d0為閾值，當傳輸距離d大于等于d0時，功率放大損耗采用多路徑衰減模型，損耗系數取4；反之，采用自由空間模型，損耗系數取2。此外，在數據融合時仍需消耗能量，用EDA表示融合單位比特數據消耗的能量。

3 三級異構網絡的分簇協議

3.1 LEACH分簇策略

LEACH協議通過輪（Round）來周期性的選擇簇頭。每輪中，每個節點都以概率Popt成為節點，建立簇時，每個節點產生0～1之間的隨機數，并于閾值函數T（s）比較，若小于T（s），則成為簇頭。

簇頭選擇結束后，每個簇頭通知其他非簇頭節點當選消息，而非簇頭節點會依據與所有簇頭通信信號的強弱判斷加入哪個簇。在穩定階段，簇頭收集來自簇內的信息，進行數據融合，傳輸至WSNs基站。

在上述閾值函數中，Popt指節點優化簇頭概率，在n個節點中，簇頭優化數量為kopt，根據文獻［12］，

由公式（4）（5）可知，Popt及kopt獨立于網絡的大小，并且只依賴于傳感器節點的數量。

LEACH協議基于同構網絡，適用于節點同質，且均勻分布的無線傳感器網絡。然而在應用中，會出現大量異質節點，如網絡運行一段時間后，節點能量必定會分布不均勻，或者網絡加入了新節點。在我們討論的模型中，假定有三類異質節點。

3.2 三級異構網絡的分簇協議

文獻［10］中，UCS假定高級節點作為簇頭，因而需要高級節點位置已知，并且分布均勻。在本文討論的協議中，所有節點都有概率成為簇頭，即不需要提前獲得節點位置信息。直觀上，我們期望高級節點和中級節點成為簇頭的概率大于普通節點，從而使得整個網絡負載均衡，延長網絡生命周期，為此，協議為不同類型節點設定不同的概率函數及閾值函數。

如前所述，網絡中存在三種類型節點，其初始能量及比例如下表：

表1 節點初始能量及數量

根據表1，三級異構網絡的初始總能量可以描述成：

如前所述，優化簇頭概率Popt只依賴于傳感器節點的數量，在三級異構網絡中，相比較于LEACH協議中的同構網絡，根據公式（6），可以理解成增加了α·m＋β·a個虛擬普通節點。為了使得網絡節點能量負載均衡，協議必須保證高級節點和中級節點當選簇頭的概率大于普通節點，即滿足如下條件：

（4）每輪當選的簇頭平均數量為n·Popt。

為此，給優化簇頭概率Popt增加權值，普通節點，中級節點和高級節點的優化簇頭概率計算公式分別如下：

4 仿真及性能評估

為驗證協議的有效性，我們分別考慮如下性能參數：

網絡生命周期：不失一般性，本文分別從第一個節點死亡時間（First Node Dies，FND），半數節點存活時間（Half of Nodes Alive，HNA）兩方面來驗證網絡生命周期。

數據吞吐量：本文比較異構網絡的數據吞吐量，分別衡量簇內節點至簇頭及簇頭至基站的數據吞吐量。

每輪簇頭平均數：為驗證協議的簇頭優化概率及簇頭優化數量，本文分析比較每輪當選簇頭的平均數量。

本文采用與LEACH協議相似的實驗參數，各項參數設置如表2所示。

表2 實驗參數

根據表2中的參數，本文使用Matlab作為仿真工具，模擬實現了LEACH協議及本文所提出的新協議，并進行性能比較分析。

4.1 網絡生命周期

圖1為網絡中采用LEACH協議及本文協議網絡存活節點數曲線圖，可以看到，采用本文協議的網絡穩定周期明顯長于LEACH協議，此外網絡的活躍時間也長于LEACH協議。為了直觀的比較網絡生命周期，圖2列出了LEACH協議及本文所提出協議的生命周期對比圖，比較了第一個節點死亡時間（FND）及半數節點存活時間（HNA），在實際的應用中，這兩中生命周期度量比最后一個節點死亡時間更加實際。由圖2可知，使用本文的協議，FND和HNA均提高了約10%的性能。這表明本文的協議考慮到異構節點的特性，并能夠更好的處理多級異構網絡，延長了網絡的生命周期。

圖1 生命周期對比圖

圖2 節點存活數曲線圖

4.2 網絡數據吞吐量

觀察圖3可知，采用本文協議的網絡數據吞吐量在生命周期內明顯高于LEACH協議。WSNs數據吞吐量包括傳感器節點至簇頭數據吞吐量，簇頭至基站數據吞吐量。本文提出的協議基于周期性數據收集應用，如環境監測等，高數據吞吐量可以更加頻繁地采集數據，高效地利用傳感器網絡。

圖3 簇頭節點數分布

圖4 網絡數據吞吐量

4.3 每輪簇頭平均數

圖4分析了每一輪選舉產生的簇頭數量分布，由圖可知，約1000輪之前，LEACH協議及本文提出的協議每輪選舉的簇頭數均分布在10左右，根據文獻［12］及公式（4），簇頭優化數量kopt只與網絡規模相關，而根據本文所采用的網絡參數，計算出kopt＝n·Popt=10，在1000輪之后，隨著部分節點能量逐漸耗盡，網絡規模逐步減少，每輪簇頭數量也隨之降低。由此可知，根據本文提出的簇頭選舉策略產生的簇頭數量與理論上所需的簇頭優化數量基本一致，從而達到網絡負載總體均衡的目的。

5 總結

在較大規模的WSNs周期性數據采集應用中，經常會出現異構網絡，或初始節點異質，或運行一段時間后產生異質節點。本文提出一種多級異構網絡的高效路由分簇協議。該協議考慮了節點的異質性，為不同類型節點設置不同簇頭選舉概率及閾值函數，優化簇頭選舉策略。實驗結果表明，本文提出的協議，能夠高效地利用傳感器網絡采集數據，網絡負載總體均衡，并延長網絡生存周期。

［1］沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議［J］.軟件學報，2006，（7）：1588-1600.

［2］Akkaya K，Younis M.A survey on routing protocols for wireless sensor networks［J］.Ad hoc networks，2005，（3）：325-349.

［3］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012，（8）：11113-11153.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］.System sciences，2000.Proceedings of the 33rd annual Hawaii international conference on.IEEE，2000：10.

［5］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection［C］.Mobile and Wireless Communications Network，2002.4th International Workshop on.IEEE，2002：368-372.

［6］Younis O，Fahmy S.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks［J］.Mobile Computing，IEEE Transactions on，2004，（4）：366-379.

［7］陳貴海，李成法，葉懋，等.EECS：一種無線傳感器網絡中節能的聚類方案［J］.計算機科學與探索，2007，（2）.

［8］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks：communication，clustering and aggregation［J］.Ad Hoc Networks，2004，（1）：45-63.

［9］Mhatre V，Rosenberg C.Homogeneous vs heterogeneous clustered sensor networks：a comparative study［C］.Communications，2004 IEEE International Conference on.IEEE，2004：3646-3651.

［10］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］.Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

［11］Smaragdakis G，Matta I，Bestavros A.SEP：A stable election protocol for clustered heterogeneous wireless sensor networks［R］.Boston University Computer Science Department，2004.

［12］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.Wireless Communications，IEEE Transactions on，2002，（4）：660-670.

TP393

A

1672-2868（2015）03-0020-06

2015-03-15

合肥學院科研發展基金一般項目（項目編號：12KY07ZR）

李新路（1980-），男，安徽無為人。合肥學院計算機科學與技術系，講師。研究方向：無線傳感器網絡。

陳 侃