節(jié)點位置信息已知的分簇算法

于南　周平

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò) 分簇算法 LEACH協(xié)議 GAF協(xié)議 位置信息

中圖分類號：TP39 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）08（a）-0192-02

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

文章的結(jié)構(gòu)安排如下：第一部分簡要分析了相關(guān)工作。第二部分詳細(xì)介紹了最大最小距離分簇算法。第三部分是仿真結(jié)果。第四部分是全文總結(jié)。

1 相關(guān)工作

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

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

2.2 算法描述

算法分為兩個階段：第一個階段尋找劃分區(qū)域的定位點，對網(wǎng)絡(luò)進(jìn)行分簇；第二個階段是選舉簇頭。

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

3 仿真結(jié)果

3.1 仿真參數(shù)設(shè)置

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

3.2 仿真結(jié)果

本文選取簇頭數(shù)方差[3]作為分簇算法性能的度量標(biāo)準(zhǔn)。簇頭數(shù)方差即簇頭數(shù)占總節(jié)點的比值是反應(yīng)了算法負(fù)載的一個重要指標(biāo)，和設(shè)置的最優(yōu)簇頭比值越接近，算法效果就越好。

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

4 結(jié)語

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

參考文獻(xiàn)

[1] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] 湯波，羅昌俊，周明天.無線傳感器網(wǎng)絡(luò)最小能量簇群構(gòu)造策略[J].計算機(jī)應(yīng)用，2007，27（1）：13-14.

[3] 何永剛，徐汀榮，彭俊.無線傳感器網(wǎng)絡(luò)分簇方法的優(yōu)化[J].計算機(jī)工程與應(yīng)用，2011，47（1）：92-94.

[4] 柳絮，李金寶，紀(jì)守領(lǐng)，郭龍江，惠麗.傳感器網(wǎng)絡(luò)簇頭選舉與調(diào)度策略研究[J].電子學(xué)報，2010，38（8）：1770-1774.