新的位置感知分簇算法

田煒，楊震

(1. 南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003；2. 南京郵電大學(xué) 信號與信息處理研究院，江蘇 南京 210003)

1 引言

在資源受限無線傳感器網(wǎng)絡(luò)（WSN）中，由于網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署、電池供能、不具備持續(xù)能量供應(yīng)等原因，能量有效性是其首要解決的問題[1,2]。而且WSN是應(yīng)用相關(guān)性非常強(qiáng)的網(wǎng)絡(luò)，只有保證數(shù)據(jù)傳輸?shù)街付ü?jié)點(diǎn)（如信宿）或區(qū)域，才能確保數(shù)據(jù)的可用性，即網(wǎng)絡(luò)的可靠性。因此在提高 WSN網(wǎng)絡(luò)能量有效性的同時，也要確保網(wǎng)絡(luò)的可靠性。

分簇網(wǎng)絡(luò)結(jié)構(gòu)由于具有良好的網(wǎng)絡(luò)擴(kuò)展性，便于能量管理、負(fù)載平衡、資源分配等特點(diǎn)，成為目前國內(nèi)外解決WSN能量有效性的主要方法之一。WSN分簇算法的典型代表 LEACH(low-energy adaptive clustering hierarchy)算法[3]，其選取簇頭的過程為：節(jié)點(diǎn)產(chǎn)生[0,1]之間的隨機(jī)數(shù)，若其小于閾值nT，則當(dāng)選為簇頭。nT的計算如式(1)所示。

其中，P是簇頭數(shù)與總節(jié)點(diǎn)數(shù)的百分比；r是當(dāng)前選舉輪數(shù)；G是當(dāng)前輪非簇頭節(jié)點(diǎn)集。

作為經(jīng)典算法，LEACH算法成為研究WSN分簇算法的主要參考。但由于 LEACH算法簇頭選取的隨機(jī)性，導(dǎo)致能量及負(fù)載不平衡。因此研究者們提出了許多新的分簇算法。如文獻(xiàn)[4]通過監(jiān)測鄰居節(jié)點(diǎn)信號功率，實(shí)時估計活動節(jié)點(diǎn)數(shù)并計算當(dāng)選簇頭的概率，提出動態(tài)分簇方法。RDCA[5]通過收集鄰居節(jié)點(diǎn)信息，根據(jù)網(wǎng)絡(luò)局部拓?fù)湫畔⑦M(jìn)行分簇。MWBC[6]先通過節(jié)點(diǎn)間的信息交互，獲得局部網(wǎng)絡(luò)信息(如節(jié)點(diǎn)度、當(dāng)前能量值、發(fā)射功率、鏈路質(zhì)量、相對位置等)，然后根據(jù)應(yīng)用背景進(jìn)行分簇決策，并預(yù)設(shè)簇的最大規(guī)模。EDCA[7]根據(jù)用戶要求的誤差門限及節(jié)點(diǎn)數(shù)據(jù)的空間相關(guān)性馬爾可夫模型，將事件感知區(qū)域劃分成虛擬極坐標(biāo)等價層，在等價層中選取剩余能量最大的節(jié)點(diǎn)作為簇頭。

但已有的分簇算法存在以下問題：1）利用網(wǎng)絡(luò)局部信息（如節(jié)點(diǎn)度、信號功率等）選取簇頭，節(jié)點(diǎn)就必須收集等待鄰居節(jié)點(diǎn)信息，勢必增大網(wǎng)絡(luò)延時，增加網(wǎng)絡(luò)控制傳輸開銷，從而降低算法的整體性能；2）采用預(yù)測模型選取簇頭，在沒有先驗(yàn)知識的前提下，往往很難得到理想的預(yù)測結(jié)果，難以適應(yīng)WSN拓?fù)淇焖僮兓奶攸c(diǎn)，使得算法實(shí)現(xiàn)困難，增加算法的復(fù)雜性；3）算法沒有考慮網(wǎng)絡(luò)的可靠性，減弱了算法的適用性。

基于位置的分簇算法因其無需建立、維護(hù)和存儲路由表，無需網(wǎng)絡(luò)拓?fù)湫畔ⅲ惴▽?shí)現(xiàn)簡單，控制開銷小等特點(diǎn)，而在WSN中得到廣泛的關(guān)注和研究。如GAF算法[8]根據(jù)節(jié)點(diǎn)位置信息將監(jiān)測區(qū)域劃分為虛擬正方形單元格，在每個單元格中定期選舉出一個簇頭節(jié)點(diǎn)。然而理論分析與仿真比較表明，蜂窩結(jié)構(gòu)更能有效地提高能量有效性，延長網(wǎng)絡(luò)壽命[9]。

因此本文在蜂窩結(jié)構(gòu)的基礎(chǔ)上，引入角度比和距離比2個參數(shù)，提出位置感知分簇算法(LACA，location aware clustering algorithm)。該算法不僅有效地提高了網(wǎng)絡(luò)能量有效性，保證網(wǎng)絡(luò)可靠性，而且算法實(shí)現(xiàn)簡單，控制傳輸開銷小。

本文第2節(jié)給出LACA的算法思想、算法分析和算法設(shè)計；第 3節(jié)給出網(wǎng)絡(luò)模型；第 4節(jié)通過NS2仿真驗(yàn)證，分析比較LEACH、GAF和LACA在能量有效性、網(wǎng)絡(luò)壽命、可靠性和分簇結(jié)構(gòu)上的性能；第5節(jié)是結(jié)束語。

2 LACA

2.1 算法思想

如圖1所示，假設(shè)以通信距離R為半徑的圓形區(qū)域是最大分簇規(guī)模，則以簇頭節(jié)點(diǎn)為中心，通信距離R為邊長的正六邊形結(jié)構(gòu)，將是最為理想的分簇結(jié)構(gòu)。然而在實(shí)際中，由于WSN部署的隨機(jī)性，無法保證簇頭節(jié)點(diǎn)正好處于正六邊形中心。因此，難以形成理想的正六邊形分簇結(jié)構(gòu)。

圖1 LACA算法思想

但是假設(shè)節(jié)點(diǎn)已知其位置信息[10～13]，則可以計算出節(jié)點(diǎn)（如節(jié)點(diǎn)13和20）之間的距離及其連線與水平線之間的夾角。通過角度比和距離比，就可以確定節(jié)點(diǎn)偏離理想簇頭位置（如節(jié)點(diǎn)10）的程度。因此，只要設(shè)置合理的角度比和距離比閾值，節(jié)點(diǎn)就可以根據(jù)角度比和距離比自主地決定是否作為簇頭，從而形成較為理想的分簇結(jié)構(gòu)。為此，本文將WSN節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)（如節(jié)點(diǎn)13，負(fù)責(zé)收集簇成員數(shù)據(jù)并轉(zhuǎn)發(fā)簇間數(shù)據(jù)）、簇成員節(jié)點(diǎn)（如節(jié)點(diǎn)30，負(fù)責(zé)監(jiān)測收集簇內(nèi)數(shù)據(jù)并將簇內(nèi)數(shù)據(jù)發(fā)送到其簇頭）和分簇網(wǎng)關(guān)節(jié)點(diǎn)（相鄰分簇相交區(qū)域內(nèi)的節(jié)點(diǎn)，如節(jié)點(diǎn)20，負(fù)責(zé)簇間數(shù)據(jù)以及簇頭形成信息的轉(zhuǎn)發(fā)），并定義

角度α

距離比

其中，Nx和 Ny表示節(jié)點(diǎn)N的橫縱坐標(biāo)，Mx和 My表示節(jié)點(diǎn)M的橫縱坐標(biāo)，R表示通信距離。

角度比η表示節(jié)點(diǎn)（如節(jié)點(diǎn)13）在角度上接近理想簇頭（如節(jié)點(diǎn)10）的程度。

距離比δ表示節(jié)點(diǎn)（如節(jié)點(diǎn)13）在距離上接近理想簇頭（如節(jié)點(diǎn)10）的程度。

LACA算法思想就是根據(jù)節(jié)點(diǎn)的位置信息，通過η和δ感知參數(shù)，在角度和距離上選取逼進(jìn)理想簇頭的節(jié)點(diǎn)作為簇頭，從而形成較為理想的分簇結(jié)構(gòu)，以此提高WSN的能量有效性，并通過η和δ閾值的合理設(shè)置，確保網(wǎng)絡(luò)的可靠性。

同時，為了避免過度消耗某節(jié)點(diǎn)的能量，有效地均衡網(wǎng)絡(luò)能量和負(fù)載，定義

偏離角度

并將式（2）修改為式（6）。角度α

引入偏離角度Δ，意味著新一輪的簇頭位于前一輪簇頭選取范圍旋轉(zhuǎn)Δ后的區(qū)域內(nèi)，從而實(shí)現(xiàn)動態(tài)輪換簇頭節(jié)點(diǎn)，有效地均衡網(wǎng)絡(luò)能量及負(fù)載。

2.2 算法分析

WSN的可靠性就是保證網(wǎng)絡(luò)數(shù)據(jù)的可用性。即網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)互達(dá)或確保數(shù)據(jù)發(fā)送到指定節(jié)點(diǎn)（或區(qū)域）。在本文中，采用孤立節(jié)點(diǎn)（與其他節(jié)點(diǎn)互不可達(dá)的節(jié)點(diǎn)）數(shù)來驗(yàn)證網(wǎng)絡(luò)的可靠性。當(dāng)孤立節(jié)點(diǎn)數(shù)為0時，表示網(wǎng)絡(luò)可靠性得到保證。η和δ的閾值就是根據(jù)孤立節(jié)點(diǎn)數(shù)為0時設(shè)置的。η越小，意味著節(jié)點(diǎn)在角度上更逼進(jìn)理想簇頭，δ越大，意味著節(jié)點(diǎn)在距離上更逼進(jìn)理想簇頭。為此，在NS2[14]仿真環(huán)境中（仿真參數(shù)如表 1所示），針對100個節(jié)點(diǎn)的網(wǎng)絡(luò)場景，具體分析η和δ閾值情況，其他網(wǎng)絡(luò)規(guī)模類似。

從圖2可知，當(dāng)η≥0.1時，孤立節(jié)點(diǎn)數(shù)為0。圖3是η=0.1時得到的δ值，從圖3中可知，當(dāng)δ≥0.6，孤立節(jié)點(diǎn)數(shù)為0。δ越大，意味著接收節(jié)點(diǎn)距離發(fā)送節(jié)點(diǎn)越遠(yuǎn)，將會由于信道衰落等原因引起誤碼，導(dǎo)致節(jié)點(diǎn)無法正確接收數(shù)據(jù)。因此，結(jié)合仿真結(jié)果，針對100個節(jié)點(diǎn)的WSN，η和δ分別設(shè)置為0.1和0.8。

表1 NS2仿真參數(shù)

圖2 角度比閾值分析

圖3 角度比確定距離比閾值分析

2.3 算法設(shè)計

2.3.1 簇頭告知信息分組結(jié)構(gòu)

節(jié)點(diǎn)當(dāng)選為簇頭后，需要向其他節(jié)點(diǎn)發(fā)送告知信息，以便其他節(jié)點(diǎn)決定是否成為該簇頭的成員。簇頭告知信息分組結(jié)構(gòu)如圖4所示。其中，NdType=0表示簇頭節(jié)點(diǎn)，NdType=1表示簇成員節(jié)點(diǎn)，NdType=2表示分簇網(wǎng)關(guān)節(jié)點(diǎn)；clsNum表示輪數(shù)，第一輪分簇設(shè)為0，以后每一輪分簇，由信宿自動加1。

圖4 簇頭告知信息分組結(jié)構(gòu)圖

圖5 LACA工作過程

2.3.2 工作過程

LACA的工作過程以“輪”進(jìn)行，每輪分為建立階段和穩(wěn)定階段2個階段，其工作過程如圖5所示。

在建立階段，信宿首先發(fā)送簇頭告知信息，將NdType設(shè)置為0，X和Y設(shè)置為其橫縱坐標(biāo)，發(fā)起新一輪的分簇過程。節(jié)點(diǎn)接收到簇頭告知信息后，按式(3)和式(4)計算η和δ。若η小于閾值，δ大于閾值，則當(dāng)選為分簇網(wǎng)關(guān)節(jié)點(diǎn)，將NdType設(shè)置為2，X和Y設(shè)置為其橫縱坐標(biāo)，并根據(jù)δ的大小，加入最小的δ分簇，同時轉(zhuǎn)發(fā)簇頭告知信息；否則，當(dāng)選為分簇成員節(jié)點(diǎn)，設(shè)置 NdType為1，并根據(jù)δ的大小，加入最小的δ分簇，同時丟棄接收到的信息分組。若節(jié)點(diǎn)接收到分簇網(wǎng)關(guān)節(jié)點(diǎn)轉(zhuǎn)發(fā)的簇頭告知信息，按式(3)和式(4)計算η和δ。若η小于閾值，δ大于閾值，則當(dāng)選為分簇簇頭節(jié)點(diǎn)，將NdType設(shè)置為0，X和Y設(shè)置為其橫縱坐標(biāo)，發(fā)送簇頭告知信息；否則丟棄接收到的信息分組。從而自動完成分簇過程，進(jìn)入穩(wěn)定階段。

在穩(wěn)定階段，分簇網(wǎng)關(guān)和簇成員節(jié)點(diǎn)持續(xù)監(jiān)測數(shù)據(jù)，并將數(shù)據(jù)發(fā)送到簇頭后轉(zhuǎn)發(fā)給信宿。持續(xù)一段時間后，進(jìn)入下一輪工作周期，由信宿開始新一輪的分簇過程，并將clsNum加1。

3 網(wǎng)絡(luò)模型

WSN模型假設(shè)如下。

1) 節(jié)點(diǎn)同構(gòu)，靜態(tài)隨機(jī)分布在二維平面上，并且節(jié)點(diǎn)自身位置已知；

2) 節(jié)點(diǎn)使用全向天線，通信距離為R(m)；

3) 最大分簇規(guī)模是以節(jié)點(diǎn)通信距離 R為半徑的圓形區(qū)域；

4) 分簇的發(fā)起節(jié)點(diǎn)為信宿。

4 仿真與性能分析

為了驗(yàn)證LACA的有效性，在NS2仿真環(huán)境中，對100個節(jié)點(diǎn)的網(wǎng)絡(luò)分析比較LEACH，GAF和LACA算法在能量有效性、網(wǎng)絡(luò)壽命、可靠性和分簇結(jié)構(gòu)上的性能。仿真參數(shù)如表1所示。正方形邊長為R / 5，正六邊形邊長為R。

并定義能量有效性γ，如式(7)所示。

其中，E總表示算法在綜合情況下（如網(wǎng)絡(luò)沖突，信道競爭，控制開銷等）消耗的總能量， ELEACH表示LEACH算法消耗的總能量。顯然γ越小，算法的能量有效性越高。

4.1 能量有效性

從圖6可知，在能量有效性上，與LEACH算法相比，GAF算法提高了約27%，LACA提高了約30%。在網(wǎng)絡(luò)運(yùn)行前期階段（200s之前），GAF算法的能量有效性優(yōu)于LACA，隨著網(wǎng)絡(luò)運(yùn)行時間的推移，LACA的能量有效性優(yōu)于GAF算法。這是因?yàn)?GAF的簇成員節(jié)點(diǎn)采用睡眠方式，并在單元格中周期性地選取簇頭，而LACA則是節(jié)點(diǎn)根據(jù)其位置信息自主地決定是否作為簇頭。

圖6 能量有效性隨時間的變化

4.2 網(wǎng)絡(luò)壽命

網(wǎng)絡(luò)壽命是指網(wǎng)絡(luò)中出現(xiàn)第一個死亡節(jié)點(diǎn)（即耗盡能量的節(jié)點(diǎn)）的網(wǎng)絡(luò)生存時間。

從圖 7可知，在網(wǎng)絡(luò)壽命上，GAF算法約為LEACH算法的2倍，LACA比GAF算法延長了約10%。LACA出現(xiàn)死亡節(jié)點(diǎn)的時間和全部節(jié)點(diǎn)死亡的時間都很晚，而且2個時間差較短，表明LACA延長了網(wǎng)絡(luò)壽命，有效地均衡了網(wǎng)絡(luò)能量和負(fù)載。

圖7 存活節(jié)點(diǎn)數(shù)隨時間的變化

4.3 可靠性

可靠性是保證網(wǎng)絡(luò)數(shù)據(jù)的可用性。當(dāng)孤立節(jié)點(diǎn)數(shù)為0時，表示網(wǎng)絡(luò)可靠性得到保證。從圖8可知，LEACH算法和GAF算法出現(xiàn)隨機(jī)性的孤立節(jié)點(diǎn)數(shù)，表明其網(wǎng)絡(luò)可靠性得不到任何保證。LACA有效地抑制了孤立節(jié)點(diǎn)的產(chǎn)生，確保了網(wǎng)絡(luò)的可靠性。這是因?yàn)長EACH算法和GAF算法沒有考慮網(wǎng)絡(luò)的可靠性，而LACA則在保證可靠性的前提下選取簇頭，其孤立節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)小于LEACH算法和GAF算法。

圖8 孤立節(jié)點(diǎn)數(shù)隨時間的變化

4.4 分簇結(jié)構(gòu)

圖9 ～圖11分別表示LEACH算法、GAF算法和LACA在第三輪分簇時形成的分簇結(jié)構(gòu)，其中實(shí)心黑點(diǎn)表示簇頭節(jié)點(diǎn)。從圖中可知，LEACH算法和GAF算法都存在孤立節(jié)點(diǎn)（圖9、圖10中畫圓圈的節(jié)點(diǎn)）。這些孤立節(jié)點(diǎn)不屬于任何分簇，既接收不到簇頭的數(shù)據(jù)，又不能將其數(shù)據(jù)匯集到簇頭，因此降低了網(wǎng)絡(luò)的可靠性。而LACA則有效地保證了網(wǎng)絡(luò)的可靠性。

圖9 LEACH算法的分簇結(jié)構(gòu)

圖10 GAF算法的分簇結(jié)構(gòu)

圖11 LACA的分簇結(jié)構(gòu)

5 結(jié)束語

針對資源受限 WSN能量有效性和可靠性問題，本文在研究分簇算法的基礎(chǔ)上，提出一種新的位置感知分簇算法（LACA）。算法采用位置感知策略選取簇頭，并依據(jù)網(wǎng)絡(luò)可靠性合理設(shè)置感知參數(shù)閾值。LACA不僅能量有效性高、網(wǎng)絡(luò)壽命長、網(wǎng)絡(luò)能量和負(fù)載均衡性好，而且有效地抑制了孤立節(jié)點(diǎn)的產(chǎn)生，保證了網(wǎng)絡(luò)可靠性。如何使算法根據(jù)網(wǎng)絡(luò)規(guī)模自適應(yīng)地改變角度比和距離比閾值，是需要進(jìn)一步研究的內(nèi)容。如何將睡眠喚醒機(jī)制引入LACA中，從而設(shè)計出更加高效的分簇算法，是下一步進(jìn)行研究的內(nèi)容。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor network[J]. IEEE Communication Magazine,2002,8∶102-114.

[2] 孫利民, 李建中, 陳渝等. 無線傳感器網(wǎng)絡(luò)[M]. 北京∶ 清華大學(xué)出版社, 2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Network[M]. Beijing∶ Qinghua University Press, 2005.

[3] HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications,2002,l(4)∶ 660-670.

[4] MING Y, LEUNG K K, MALVANKAR A. A dnamic clustering and energy efficient routing technique for sensor networks[J].IEEE Trans on Wireless Communications, 2007, 6(8)∶3069-3079.

[5] 胡靜,沈連豐,宋鐵成等.新的無線傳感器網(wǎng)絡(luò)分簇算法[J].通信學(xué)報,2008, 29(7)∶20-26.HU J, SHEN L F, SONG T C, et al. Novel clustering algorithm for wireless sensor networks[J]. Journal on Communications,2008, 29(7)∶ 20-26.

[6] 黃河清,姚道遠(yuǎn),沈杰等.一種基于多權(quán)值優(yōu)化的無線傳感網(wǎng)分簇算法的研究[J].電子與信息學(xué)報,2008,30(6)∶1489-1492.HUANG H Q, YAO D Y, SHEN J, et al. A multi-weight based clustering algorithm for wireless sensor networks[J]. Journal of Electronics &Information Technology, 2008,30(6)∶1489-1492.

[7] 王天荊, 楊震, 胡海峰. 基于空間相關(guān)性的事件驅(qū)動無線傳感器網(wǎng)絡(luò)分簇算法[J]. 電子與信息學(xué)報,2008,30(3)∶699-702.WANG T J, YANG Z, HU H F. An event driven clustering algorithm based on spatial correlation in wireless sensor networks[J]. Journal of Electronics & Information Technology, 2008,30(3)∶699-702.

[8] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[A]. Proc of 7th Annual Int’l Conf on Mobile Computing and Networking[C]. Rome , Italy ACM Press,2001.70 - 84.

[9] WANG Z, ZHANG J. Energy efficiency of two virtual infrastructures for MANETs[A]. Performance, Computing and Communications Conference , 2005 , IPCCC 2005, 24thIEEE International[C]. Phoenix,Arizona, USA∶ IEEE Press, 2005. 547 - 552.

[10] HOFMANN WELLENHOF B, LICHTENEGGER H, COLLINS J.Global Positioning System∶ Theory and Practice[M]. Springer Verlag,1997.

[11] BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications Magazine, 2000, 7(5)∶ 28-34.

[12] CARUS A, URPI A, CHESSA S, DE S.GPS-free coordinate assignment and routing in wireless sensor networks[A]. Proc 24th Annu Joint Conf. IEEE Comput Commun Soc (INFOCOM ’05)[C]. 2005,1∶150-160.

[13] WARD A, JONES A, HOPPER A. A new location technique for the active office[J]. IEEE Personal Communications, 1997,4(5)∶ 42-47.

[14] The network simulator-ns-2[EB/OL]. http∶//www.isi.edu/ nsnam/ns/index.html.2008.