無線傳感器網絡中混合簇頭選舉算法的研究

摘要：針對網絡拓撲結構穩定的實際應用，提出了一種混合簇頭選舉算法，包括以質心(能量中心)為基礎的簇頭選舉方式和以剩余能量為基礎的簇頭選舉方式。通過降低系統內簇頭與簇內節點之間通信的總能量和平均傳輸時延來提高網絡的生命周期。仿真結果表明，與GAF算法相比，網絡的生命周期得到了較大幅度的提高，并且隨著單簇節點數的增加，網絡的生命周期也隨之增加。實驗證明，該方法適用于組建大規模無線傳感器網絡。

關鍵詞：無線傳感器網絡； 混合簇頭選舉算法； 地理位置； 質心

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)04－1227－03

作為一種全新的信息獲取和處理技術，無線傳感器網絡[1]已在軍事、環境科學、醫療健康、空間探索及其他商業領域得到廣泛應用[2]。

無線傳感器網絡涉及的關鍵技術包括網絡拓撲控制、網絡協議、網絡安全、時間同步、定位技術、數據管理、無線通信技術等[2]。層次型的拓撲結構由于具有減少通信量、有利于分布式計算、可擴展性強、能量利用效率高、數據融合簡單、適合大規模部署網絡等特點，成為當前拓撲控制研究的重點。

層次型拓撲結構的分簇算法主要包括LEACH[3]及其改進算法LEACH－C(LEACH－centralized)[4]和LEACH－F（LEACH－fixed）[4]、PEGASIS[5]、HEED[6] 、ACE[7]、GAF[8]及其改進算法等。這些算法中除GAF(geographical adaptive fidelity)及其改進算法外，通常是先選舉出簇頭，再通過簇頭組織簇，并且均未考慮節點的位置信息。但在很多應用中，如工業監測，節點位置已經布好，并且已知節點的監測類型。因此，分簇情況比較明顯，這就使得簇的形成先于簇頭的形成，與現有的算法存在較大的差別。GAF算法中先對監測區域劃分虛擬單元格，在每個單元格內節點使用競爭的方式來競爭簇頭，沒有充分考慮節點的剩余能量，并且節點處于偵聽狀態時消耗能量較大，降低了網絡使用壽命。在隨后的GAF改進算法中，優化了簇頭選舉方式，但要求節點具有嚴格的時間同步。本文結合工業現場監測特點，以節點地理位置為研究基礎，針對監測區域內節點的數量，提出了根據簇內節點個數的不同，采用新的簇頭選舉算法，在充分考慮節點的能量消耗的情況下采用能量中心和剩余能量為基礎的動態簇頭選舉算法，使得簇內的每個節點的能耗均衡，從而提高網絡的生命周期。

1約束條件和相關模型

本文所描述的算法遵循以下約束條件：a)為了避免網絡拓撲結構頻繁改變，假定節點是微移動或靜止不動；b)網絡節點組織成簇結構的形式，簇頭執行數據的融合功能，并負責將集中后的數據傳輸到匯聚節點；c)每個傳感器節點在每一輪數據采集過程中所產生的數據量是相同的; d)簇內成員不會轉發其他傳感器節點的數據，簇內節點之間不發生通信；e) 簇內節點和簇頭節點的發射功率一定，并且簇內節點與簇頭節點之間均在一跳通信范圍內；f) 節點具有較大的存儲容量。網絡拓撲結構模型如圖1所示。

能耗模型采用無線通信能耗模型[9]，如圖2所示。在該模型中，發送節點的能量消耗包括無線發送裝置和放大器兩部分，接收節點的能量消耗來自于接收裝置的能量消耗。在圖2中，包括自由空間(d2功率損失)和多徑衰落(d4功率損失)兩種通道模型。實驗中使用何種模型取決于發送節點與接收節點之間的距離。如果發送節點與接收節點之間的距離小于閾值d0，則使用自由空間模型，否則使用多徑衰落模型。

2算法描述

2．1算法核心思想和關鍵點說明

考慮到節點通過發送數據包進行信息交互來選舉簇頭的方式將消耗大量的能量。本文提出算法中對節點的剩余能量采用估計的方式。節點通過式(1)~(6)及質心公式對每個節點的剩余能量進行估計。這樣在每個節點通過計算就可大致獲得所在簇的質心(能量中心)。考慮到計算節點剩余能量與真實情況會存在偏差，系統會在每個周期(簇內所有成員均當選過一次簇頭稱為一個周期)之后，通過發送數據包的方式來修正每個節點由于計算所得的剩余能量的值。

1) 關鍵結構說明

本算法在簇頭選舉的過程中主要依靠節點的計算，保存在節點flash中的結構信息的值并不能真實地反映節點的剩余能量。計算所得的節點的剩余能量可能會與實際情況存在一定的偏差，系統會在每個周期(簇內成員均分別成為一次簇頭稱為一個周期)后通過一次信息交互來更新簇內節點的剩余能量。因此要求節點具有較大的存儲空間，簇內的每個節點要保存簇內成員的相關信息。簡單地說，如果簇內有n個節點就要保存n個這樣的結構，在每完成一輪計算后就會更新節點的相關信息。簇內成員的相關信息存儲的結構如下：

StructNode_Info

{

 int[n]Node_Id;//節點的ID

 float[n]Distance_Node_to_Cluster; //簇內成員到簇頭的距離

 float[n]Node_Compute_Energy;//節點通過計算得到的剩余能量

 float[n]Node_Real_Energy//簇內節點的真實剩余能量

 float[n]Node_CoordinateX;//節點的x軸坐標值

 float[n]Node_CoordinateY;//節點的y軸坐標值

};

其中：n表示簇內節點個數。

2) 簇的形成

首先由匯聚節點廣播一個開始建立簇的消息。節點收到消息后采用洪泛或者廣播的形式反饋消息。節點消息中包括監測區域、監測量類型、節點ID、剩余能量、坐標值。由于每個節點的位置是固定的，可由人工事先進行簇的劃分。

3) 簇頭選舉

針對簇內節點的數量采用不同的簇頭選舉方式。如果簇內節點數量超過一定的值，采用基于質心的簇頭選舉方式。通過簇內節點坐標可以求出這個簇的質心(能量中心)。如果質心位置恰好有節點，那么該節點即作為本輪的簇頭；如果質心位置沒有節點，那么求出每個節點到質心的距離，將距離最近的節點作為本輪的簇頭。當出現具有多個節點到質心距離相等的情況，選擇節點ID號最大的作為本輪的簇頭。在下一輪的簇頭選舉中，將前面已經當過簇頭的節點排除掉，保證簇內所有的節點依次成為簇頭。如果簇內節點少于一定數量，則根據節點的剩余能量對該簇進行簇頭選舉，每輪選擇剩余能量最多的節點成為簇頭；如果出現兩個節點的剩余能量完全相同，則選擇節點ID號較大的作為簇頭。下一輪選舉時，排除前面已經當選過簇頭的節點，直到該簇內所有節點均當選過一次后，依此進行循環。

2．2算法實現關鍵步驟

1) 簇頭選舉

根據簇內節點的不同數量，分別進行如下處理:

a)簇內節點數量超過n。根據質心公式求得每個簇的質心所在位置。依此比較簇內每個節點與質心的坐標值，將距離質心最近，并且前面未當選過簇頭的節點，作為本輪的簇頭。將當選的簇頭類型置為“C”，非簇頭節點用“N”表示。

質心(能量中心)計算公式為：

=Ey/E=∑ni=1eixi/∑ni=1ei，

=Ex/E=∑ni=1eiyi/∑ni=1ei

其中：ei為節點的剩余能量；xi為節點橫坐標值；yi為節點縱坐標值。

b)簇內節點數不超過n。這時簇內節點的數量較少，根據簇內節點的剩余能量，選擇剩余能量最多，并且在前面沒有被選舉為簇頭的節點作為本輪的簇頭。同樣，將當選的簇頭類型置為“C”，非簇頭節點用“N”表示。

2) 簇頭分配時隙

a）簇頭節點在簇內廣播消息，消息內容包括節點ID、剩余能量、電池電量、坐標值，通知簇內節點自己當選簇頭，并將自己的類型置為“C”(簇頭標志)。簇內非簇頭節點收到消息后會返回消息，也包括同樣的內容，并將類型置為“N”。

b）簇頭作為每輪的控制中心產生TDMA的規則，并將這個規則發布給簇內的其他節點。這樣確保簇內節點發送數據信息時不會產生沖突。簇內非簇頭節點在接收到該規則后進入休眠狀態，只有在規定的時隙內醒來后發送數據，減少了單個節點的能量消耗。

當所有的節點均當選過簇頭之后，將節點的類型全部置為非簇頭，再依此循環執行。該算法流程如圖3所示。

3仿真試驗與分析

基于上文提到的混合簇頭選舉算法，下面將通過量化分析手段來描述網絡生命周期與初始能量之間的關系。算法結束的條件是網絡中出現第一個能量耗盡的節點。本文算法能耗包括簇內節點和簇頭節點的能耗。簇內節點的能耗主要是發送數據給簇頭的能耗。簇頭節點的能耗包括接收簇內節點數據的能耗、融合數據的能耗和將融合后的數據包發給基站的能耗。在每個周期(簇內節點均當過一次簇頭稱為一個周期)之后，節點修正結構中的計算剩余能量所產生的能耗。仿真實驗分兩步進行，試驗中使用的通用參數如表1所示。

第一步，首先比較本文中提出的兩種算法，確定出單簇內節點個數的閾值。表1給出了實驗中所使用的參數。單簇的節點數的閾值為n，節點在區域內隨機分布。如果簇內節點大于n，則采用基于質心的簇頭選舉算法；如果不大于n，則采用基于節點剩余能量的簇頭選舉算法。考慮到本算法的簇是靜態穩定的，單簇的網絡生命周期直接決定整個網絡的生命周期。因此在進行仿真實驗時，只對本文提出的算法進行單簇比較。單簇節點數目分別為5、8、10，比較結果如圖4所示。 

根據圖4(a)可知，當簇內節點數為10時，基于質心的簇頭選舉算法的生命周期大于基于剩余能量的簇頭選舉算法的生命周期；由圖4(b)可以看出，當簇內節點數為8時，基于質心的簇頭選舉算法和基于剩余能量的簇頭選舉算法的生命周期相差不大；由圖4(c)可以看出，當簇內節點數為5時， 基于剩余能量的簇頭選舉算法的生命周期大于基于質心的簇頭選舉算法。由實驗可知，簇內節點數目的不同，選擇不同的簇頭選舉算法，能夠提高整個網絡的生命周期。

第二步，將本文提出的算法與GAF算法進行比較，從而可以看出整個網絡生命周期的情況。實驗中將整個網絡分為4個簇，每簇的節點個數分別為5、8、10、20。節點分布如圖5所示。根據第一步的實驗結果，節點數為5和8時，采用基于剩余能量的簇頭選舉算法，節點數為10和20時，采用基于能量中心的簇頭選舉算法。比較結果如圖6所示。



圖6比較了混合簇頭選舉算法與GAF算法在單簇節點個數、節點初始能量發生變化時，網絡生命周期之間的關系。從圖中可以看出，相對GAF算法，混合簇頭選舉算法的網絡生存周期會有較大幅度增加。在混合簇頭選舉算法中，簇頭選舉主要依靠節點自身計算，相比GAF及其改進算法，節省了簇內成員由于競爭簇頭而需要發送的數據包所消耗的能量。Pottie等人提出在無線環境下，執行3 000條指令相當于無線模塊將1 bit信息發送到100 m的終端所消耗的能量[10]。理論上可知，混合簇頭選舉算法將較大幅度地提高網絡生命周期。

通過仿真實驗可知，混合簇頭選舉算法隨著單簇節點數的增加網絡的生命周期也會相應增加，其原因是相同時間內，簇內節點數少的簇內成員成為簇頭的次數多，簇頭會消耗較大的能量。本文提出的算法相對于GAF算法更適合于組建較大規模的傳感器網絡。實驗中節點是隨機分布的，當節點位置發生變化時，網絡的生命周期波動較小，具有很好的穩定性。

4結束語

本文針對一些特定應用，如工業現場監測，根據簇內節點數量的不同，提出了混合簇頭選舉算法的策略，完善了以質心為研究基礎的簇頭選舉算法。通過實驗可以看出，該方法可以提高整個網絡的生命周期，并且隨著簇內節點數的增加網絡的生命周期也相應增加。因此，這種策略非常適合組建大規模的無線傳感器網絡監測系統，為建立無線傳感器網絡監測系統提供一個全新的方案。

參考文獻：

［1］ILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8):102－114.

[2］FY， HUANG H N， LIN C. Wireless sensor networks [J].Journal of Software，2003，14(7):1282－1291.

[3]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energy－efficient communication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Annual Hawaii Int’l Conf on System Sciences. Maui: IEEE Computer Society， 2000. 3005－3014.

[4]HEINZELMAN W. Application－specific protocol architectures for wireless networks [D]. Boston: Massachusetts Institute of Technology， 2000.

[5］LINDSEY S， RAGHAVENDRA C S. PEGASIS: power－ efficient gathering in sensor information systems[C]//Proc ofIEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society， 2002: 1125－1130.

[6］YOUNIS O， FAHMY S. Heed: a hybrid， energy－ efficient， distributed clustering approach for Ad hoc sensor networks[J]. IEEE Trans on Mobile Computing， 2004，3(4):660－669.

[7］CHAN H， PERRIG A. ACE: an emergent algorithm for highly uniform cluster formation[C]//Proc of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920. Berlin: Springer－Verlag， 2004: 154－171.

[8］XU Y， HEIDEMANN J， ESTRIN D. Geography informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual Int’l Conf on Moblie Computing and Networking (MobileCOM). 2001: 70－84.

[9］HEINZELMAN W R， CHANDRAKASAN A， BALAKRISLMAN H. Energy－efficient communication protocol for wireless microsensor networks[C]//Proc ofHawaii International Conference on System Sciences. Maui， Hawaii:[s.n.]， 2000.

[10］POTTIE G J， KAISER W J. Embedding the internet: wireless integrated network sensors[J]. Communications of the ACM， 2000，43(5):51－58，

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”