節點位置信息已知的分簇算法

于南　周平

摘 要：無線傳感器網絡是一種無線自組織網絡，并由大量的傳感器節點構成。本文研究了典型的分簇協議，并在此基礎上提節點位置信息已知的分簇算法出了一種新的分簇算法—— 最大最小距離分簇算法（max-min distance clustering algorithm）。該算法在節點位置信息已知的情況下，引入定位點為參量，可確保每輪選出理想的簇頭個數。

關鍵詞：無線傳感器網絡 分簇算法 LEACH協議 GAF協議 位置信息

中圖分類號：TP39 文獻標識碼：A 文章編號：1672-3791（2014）08（a）-0192-02

無線傳感器網絡（Wireless Sensor Networks，WSNs）就是由部署在監測區域內大量的廉價微型傳感器節點組成，通過無線通信方式形成的一個多跳自組織的網絡系統，其目的是協作地感知，采集和處理網絡覆蓋區域中感知對象的信息，并發送給觀察者[1]。網絡中節點通常只配備容量有限的電池提供能量，并且在使用過程中，對節點電池進行充電或更換電池幾乎是不可能的[2]。所以網絡生存期的長短是決定無線傳感器網絡功效的重要因素[3]。針對傳感器網絡的特殊環境，已經提出了許多適合于不同網絡環境的路由協議，分簇路由協議具有能量利用高效、數據融合簡單等優點，因此成為當前重點研究的路由算法[4]。

文章的結構安排如下：第一部分簡要分析了相關工作。第二部分詳細介紹了最大最小距離分簇算法。第三部分是仿真結果。第四部分是全文總結。

1 相關工作

分簇路由協議的設計大致包括以下3個階段：（1）簇頭的產生；（2）簇的形成；（3）簇的路由[5]。在現有的文獻中，一部分文獻提出的分簇算法的思想是先產生簇頭，再形成簇，例如：LEACH協議，HEED協議，TEEN協議等。LEACH（Low Energy Adaptive Clustering Hierarchy）協議[6]是節點根據某個閾值自主決定是否當選簇頭，簇頭的選擇具有隨機性。HEED（A Hybrid， Energy-Efficient， Distributed Clustering Approach）協議[7]是通過節點之間的信息交互動態產生簇頭，在簇頭的選擇過程中考慮了節點的剩余能量，并以主從關系引入了多個約束條件作用于簇頭的選擇過程。而TEEN協議[8]是針對事件監測類型的WSNs而設計的路由策略，它具有實時性，可以對突發事件做出快速反應。

在上述分簇算法中，簇頭的產生是簇形成的基礎。而另一部分文獻則是先劃分區域形成簇，再從每個區域中依照某種準則選擇簇頭。例如：GAF分簇協議。GAF（geographical adaptive fidelity）算法[9]是根據節點的位置信息將監測區域劃分為虛擬正方形單元格，在每個單元格中定期選舉出一個簇頭節點。

2.2 算法描述

算法分為兩個階段：第一個階段尋找劃分區域的定位點，對網絡進行分簇；第二個階段是選舉簇頭。

第一個階段尋找定位點分簇。網絡中隨機部署了N個節點，節點當選簇頭的概率為P，最優簇頭數為K，則有，每個簇內的節點總數理論上的最優值為N/K。設網絡中存活的節點集合為G，首先進行第一次的區域劃分，在G中隨機選擇一個節點A，由于網絡節點位置信息已知，可計算出與A節點距離最遠的節點B。因為B節點距離A點最遠，所以不適宜把A，B兩點劃到同一個簇中，則A，B兩點可分別為兩個簇的定位點。A、B兩點間的距離即“最大最小距離分簇算法”中的“最大距離”。之后A節點選擇距離自己最近的（N/K-1）個節點，形成簇，Ga，此為“最小距離”之意。已經加入簇Ga的節點不能再加入其它的簇。同理以B節點為定位點，在節點集合（G-Ga）中找到距離自己最近的（N/K-1）個節點，形成簇Gb。節點A和B就是在第一次劃分簇過程中所找到的一對定位點。第二次劃分是在剩余的未加入簇Ga，Gb的節點集合（G-Ga-Gb）中找到距離最遠的兩個節點C和D，分別以節點C，D為定位點，形成簇Gc和簇Gd，成簇過程與Ga和Gb相同。如果K為偶數2n（n為自然數），則需要進行n劃分，每次劃分都會找到一對定位點，n次劃分之后，網絡中的所有節點都被劃分到了相應的簇內。如果K為奇數2n+1（n為自然數），同樣進行n次劃分，每次劃分找到一對定位點，但是與K為偶數不同的是，n次劃分后，最后會剩下N/K個節點，則剩余的N/K個節點自然形成最后一個簇。

3 仿真結果

3.1 仿真參數設置

本文采用MATLAB對算法進行仿真。設節點總數N為100，節點的初始能量為0.2J，數據包大小為4000比特，基站的坐標位置為（50，175），理想簇頭百分比P為0.05。

3.2 仿真結果

本文選取簇頭數方差[3]作為分簇算法性能的度量標準。簇頭數方差即簇頭數占總節點的比值是反應了算法負載的一個重要指標，和設置的最優簇頭比值越接近，算法效果就越好。

圖1顯示了LEACH算法，GAF算法和最大最小距離分簇算法在簇頭數方差上的對比情況。實驗中LEACH算法和最大最小距離分簇算法的最優簇頭數都為5，GAF算法的最優簇頭數為4。從圖1中可以看出，LEACH算法的簇頭數方差波動最大，GAF算法次之，最大最小距離分簇算法的簇頭數方差波動最小，明顯優于LEACH算法和GAF算法，說明該算法可以保證每輪都選出理想的簇頭數目，抑制了所選簇頭個數過多或過少，均衡了節點的能耗。

4 結語

針對無線傳感器網絡的可靠性和能量的有效性等問題，本文在對LEACH協議和GAF協議研究的基礎上，提出了一種新的基于節點位置信息已知的分簇算法。算法引入了定位節點先劃分簇，再從已劃分得的簇中，選出最優位置的簇頭。仿真證明，最大最小距離分簇算法與LEACH協議和GAF協議相比，可以確保每輪都選出最優的簇頭數目，使得每輪節點的總能耗最小。

參考文獻

[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2] 湯波，羅昌俊，周明天.無線傳感器網絡最小能量簇群構造策略[J].計算機應用，2007，27（1）：13-14.

[3] 何永剛，徐汀榮，彭俊.無線傳感器網絡分簇方法的優化[J].計算機工程與應用，2011，47（1）：92-94.

[4] 柳絮，李金寶，紀守領，郭龍江，惠麗.傳感器網絡簇頭選舉與調度策略研究[J].電子學報，2010，38（8）：1770-1774.