基于簇結(jié)構(gòu)穩(wěn)定的分環(huán)多跳路由算法＊

周建欽，石志遠(yuǎn)，趙澤茂

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州 310018）

基于簇結(jié)構(gòu)穩(wěn)定的分環(huán)多跳路由算法＊

周建欽，石志遠(yuǎn)，趙澤茂

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州 310018）

為了提高大型無線傳感器網(wǎng)絡(luò)的穩(wěn)定性，延長網(wǎng)絡(luò)出現(xiàn)首個節(jié)點的死亡時間，提出一種基于簇結(jié)構(gòu)穩(wěn)定的分環(huán)多跳路由算法CBSM（Cluster structure stability based Sub－ring algorithm over multi－h(huán)op routing）.CBSM算法將監(jiān)測區(qū)域劃分為許多固定小區(qū)，采用基于節(jié)點剩余能量和節(jié)點位置的代價函數(shù)選擇簇頭.仿真結(jié)果表明，基于簇結(jié)構(gòu)穩(wěn)定的多跳路由算法，能有效延長網(wǎng)絡(luò)出現(xiàn)首個節(jié)點死亡的時間，提高整個網(wǎng)絡(luò)的穩(wěn)定性.

固定分區(qū)；分簇路由；最優(yōu)簇頭數(shù)目；簇心；相對距離

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

文中假設(shè)N個傳感器節(jié)點隨機(jī)、均勻的分布在半徑為R的圓形區(qū)域內(nèi)，同時有以下假設(shè)：

（1）所有節(jié)點初始能量相同，節(jié)點部署完畢后不再移動.

（2）節(jié)點裝備有定位裝置，可以感知自身地理位置.

（3）基站（BS）位于圓形區(qū)域的中心且位置固定，基站能量不受限制.

（4）節(jié)點能確保與所在分區(qū)內(nèi)的任意一個節(jié)點保持通信.

為了方便不同簇間多跳路由路徑的建立，按照實際需要將整個感知區(qū)域均勻等分為h個圓環(huán)，寬度為a＝R／h.從以基站為圓心的圓向外，依次標(biāo)注為第1環(huán)、第2環(huán)、……、第h環(huán).節(jié)點部署完成后向基站發(fā)送NODE＿M(jìn)消息，其中包含節(jié)點的位置信息（posi，x，posi，y）和節(jié)點當(dāng)前能量信息Ei－current.基站收到節(jié)點發(fā)送來的信息后，根據(jù)實際需求計算感知區(qū)域最佳分環(huán)數(shù)h.

2 算法描述

2.1 最優(yōu)分區(qū)數(shù)目

無線傳感器網(wǎng)絡(luò)中，靠近基站的簇頭節(jié)點因為要轉(zhuǎn)發(fā)數(shù)據(jù)，其能量消耗要大于外環(huán)簇頭的能量消耗，很容易因為能耗問題而過早“死亡”.為了避免出現(xiàn)數(shù)據(jù)傳輸過程中的“熱點”問題，均衡不同環(huán)內(nèi)簇頭的能量消耗，筆者在不同環(huán)內(nèi)劃分規(guī)模不同的簇來解決簇頭能耗不均的弊?。?］.具體來說就是：基站根據(jù)全網(wǎng)總體信息利用文獻(xiàn)［4］中方法計算出各環(huán)最優(yōu)簇頭數(shù)目后，按照各環(huán)最優(yōu)簇頭數(shù)目mk（k＝1，2，...，h）將網(wǎng)絡(luò)區(qū)域進(jìn)行分區(qū).分區(qū)模型建立完畢后，基站將區(qū)域總體信息和各環(huán)分區(qū)信息hzone、分區(qū)平均能量Eave以及基站位置posBS打包DATA＝｛N，R，h，hzone，Eave，posBS｝，并將其標(biāo)注為BS＿TOTAL＿M(jìn)EG向整個網(wǎng)絡(luò)區(qū)域廣播.網(wǎng)絡(luò)區(qū)域中的任一節(jié)點在接收到BS＿TOTAL＿M(jìn)EG消息后，將其自身位置信息與基站（BS）位置信息進(jìn)行比較，以此來確定自己所在的環(huán)數(shù)和分區(qū)位置，方法為

則節(jié)點i位于第k環(huán)內(nèi).其中D（·）為距離運(yùn)算，

圖1 網(wǎng)絡(luò)分區(qū)模型

利用以上方法，節(jié)點可以從集合DATA中找到自身所在的環(huán)數(shù)以及所在環(huán)的分區(qū)信息，各環(huán)按照分區(qū)信息進(jìn)行分區(qū)，每個小分區(qū)即為一個簇.分區(qū)模型如圖1所示.

文中采用文獻(xiàn)［6］中提出的無線能量消耗模型.節(jié)點發(fā)送數(shù)據(jù)的能量消耗為

接收端消耗的能量為

其中：Eelec表示無線收發(fā)電路發(fā)送或接受1bit數(shù)據(jù)時的能耗；εfs和εmp分別表示自由空間模型和多路衰減模型的損耗系數(shù)；d0為常數(shù)；L是要發(fā)送或接收的數(shù)據(jù)比特數(shù).

2.2 簇頭選舉

整個感知區(qū)域分區(qū)完畢后，基站計算各分區(qū)的平均能量Eave，并向全網(wǎng)廣播.網(wǎng)路中任意節(jié)點i將接收到的自己分區(qū)的平均能量值與自身剩余能量比較，能量小于分區(qū)平均能量的節(jié)點放入集合Emin中.由于平均能量的計算需要全網(wǎng)節(jié)點的剩余能量信息，對于大型傳感器網(wǎng)絡(luò)來說能量消耗十分巨大，因此文中采用估計方法來預(yù)測每一輪各個分區(qū)的平均能量［7］.假設(shè)傳感器節(jié)點每輪消耗相同的能量，這種假設(shè)是合理的，因為采用固定分區(qū)策略每輪的簇頭數(shù)量相同，通信開銷相近.

由文獻(xiàn)［6］所示無線通信能耗模型可得第k環(huán)中任一簇頭的能耗為

由文獻(xiàn)［4］得第1環(huán)內(nèi)某個成員節(jié)點的能耗為

由假設(shè)條件可以預(yù)測經(jīng)過r輪后第k環(huán)內(nèi)某個分區(qū)的平均能量為E＝Etotal－r·（Echk＋Enon－ch1）k＝1，2，...，h，

經(jīng)過r輪后第k環(huán)內(nèi)任意節(jié)點剩余能量為：

（1）節(jié)點上一輪為成員節(jié)點時，Ere＝E0－r·Enon－ch1；

（2）節(jié)點上一輪為簇頭結(jié)點時，Ere＝E0－r·Echk，k＝1，2，...，h.

定義1 一個簇內(nèi)所有節(jié)點位置坐標(biāo)的平均值稱為一個簇的主簇心，即節(jié)點的坐標(biāo)質(zhì)心［8］.其數(shù)學(xué)表達(dá)式為：設(shè)第k環(huán)某個簇內(nèi)的任一節(jié)點i（i＝1，2，...，（Nk／mk）），節(jié)點的位置用posi，x和posi，y表示，則簇心坐標(biāo)（主簇心坐標(biāo)包含在分區(qū)信息hzone中向全網(wǎng)廣播）表示為

分區(qū)中任意節(jié)點i到簇心的距離為

同理，將一個簇內(nèi)所有剩余能量小于簇平均能量的節(jié)點位置坐標(biāo)的平均值定義為副簇心.設(shè)第k環(huán)某個簇內(nèi)集合Emin中有m個節(jié)點，集合中的任一節(jié)點j（j＝1，2，...，m）節(jié)點的位置用posj，x和posj，y表示，則副簇心坐標(biāo)（副簇心坐標(biāo)包含在分區(qū)信息hzone中向全網(wǎng)廣播）表示為

集合Emin中任意節(jié)點j到副簇心的距離為

從而，主簇心與副簇心之間的相對距離為D＝｜D（i）－D（j）｜.

為了使簇內(nèi)節(jié)點保留更多的能量用來傳遞簇間數(shù)據(jù)，同時盡量延長第1個節(jié)點的死亡時間，采用基于節(jié)點剩余能量和節(jié)點位置的代價函數(shù)的方法選舉簇頭，使當(dāng)選的簇頭剩余能量盡可能大并且使當(dāng)選簇頭節(jié)點到主、副簇心的相對距離盡量小.（當(dāng)選簇頭剩余能量足夠大才會在傳遞簇間數(shù)據(jù)時不至于過早死亡而使得網(wǎng)絡(luò)癱瘓，相對距離盡可能小可以減少大部分節(jié)點向簇頭傳輸數(shù)據(jù)時的能耗，延長其生存時間.）

由節(jié)點到主、副簇心的相對距離和節(jié)剩余能量設(shè)定權(quán)值

簇頭選舉時，在第k環(huán)的某個分區(qū)內(nèi)的節(jié)點i首先從基站發(fā)送來的DATA信息中查找到自己所在分區(qū)的平均能量Eave和主、副簇心坐標(biāo)判定自己所屬的集合，并利用（1）和（2）式計算出節(jié)點到主、副簇心的距離D（i）和D（j）.然后，節(jié)點i利用（3）式求出代價權(quán)值W，權(quán)值W設(shè)定完畢后，節(jié)點將自身權(quán)值向所在分區(qū)內(nèi)廣播.節(jié)點i將接收到其他節(jié)點的權(quán)值信息與自身權(quán)值進(jìn)行比較，若存在權(quán)值比自身大的節(jié)點，則該節(jié)點i退出簇頭競爭成為成員節(jié)點，否則宣布自己當(dāng)選為簇頭.

當(dāng)選為簇頭的節(jié)點以固定功率f向外發(fā)送CH＿ELECTED＿M(jìn)SG消息，消息中包含當(dāng)選簇頭節(jié)點的地理位置以及能量信息.分區(qū)內(nèi)其他節(jié)點接收到此消息后檢查發(fā)送此消息的節(jié)點是否與自己在同一分區(qū)，若是則退出簇頭競爭，并向當(dāng)選的簇頭節(jié)點發(fā)送NODE＿JOIN＿M(jìn)SG消息，加入該簇.簇頭接收到NODE＿JOIN＿M(jìn)SG消息后返回一個ACP＿M(jìn)SG消息將節(jié)點加入到本簇.第（k＋1）環(huán)中的簇頭節(jié)點接收到來自第k環(huán)的簇頭消息后，在第k環(huán)當(dāng)選簇頭中選擇下一跳路由節(jié)點.

2.3 下一跳路由節(jié)點

傳輸1bit的數(shù)據(jù)消耗的能量遠(yuǎn)大于處理1bit數(shù)據(jù)所消耗的能量，位于內(nèi)環(huán)的簇頭在數(shù)據(jù)傳輸過程中要轉(zhuǎn)發(fā)外環(huán)數(shù)據(jù)，若是外環(huán)簇頭選擇下一跳路由節(jié)點算法不合理，則會造成內(nèi)環(huán)某些簇頭成為多個外環(huán)簇頭的中繼節(jié)點，或某些內(nèi)環(huán)簇頭節(jié)點處于相對空閑狀態(tài).這種情況會造成節(jié)點的能量消耗不均勻，導(dǎo)致內(nèi)環(huán)某些簇頭節(jié)點因轉(zhuǎn)發(fā)數(shù)據(jù)量過大而過早“死亡”，從而影響整個網(wǎng)絡(luò)的穩(wěn)定性.

為了解決這個問題，筆者提出依據(jù)能耗均衡原則選擇下一跳路由節(jié)點.所謂能耗均衡原則，就是能量低的簇頭在選擇下一跳路由節(jié)點時選擇距離近的簇頭節(jié)點，能量高的節(jié)點選擇距離遠(yuǎn)的簇頭節(jié)點作為下一跳路由節(jié)點.具體算法描述為：第（k＋1）環(huán)中的簇頭節(jié)點接收到第k環(huán)簇頭節(jié)點發(fā)送來的CH＿ELECTED＿M(jìn)SG消息后，根據(jù)自身位置計算與第k環(huán)內(nèi)簇頭之間的距離d.第（k＋1）環(huán)中的簇頭首先選擇距離d最小的第k環(huán)內(nèi)簇頭作為下一跳路由節(jié)點，第k環(huán)中的簇頭節(jié)點將選擇自己作為下一跳路由的第（k＋1）環(huán)中的簇頭節(jié)點放入集合R－NODE中，然后集合中的節(jié)點數(shù)大于2個時，集合中的節(jié)點比較彼此的能量大小，能量最大的節(jié)點退出該集合，選擇距離自己次近的第k環(huán)中簇頭作為下一跳.以此類推，直到所有簇頭節(jié)點選擇到合適的下一跳路由節(jié)點.

2.4 算法流程

CBSM算法的運(yùn)行過程主要分為3個階段：分區(qū)、簇頭選擇和數(shù)據(jù)傳輸.其中數(shù)據(jù)傳輸階段按照TDMA方式，簇內(nèi)不同節(jié)點按照事先劃分的時隙向簇頭傳輸數(shù)據(jù)，TDMA信息包含在簇頭建立階段發(fā)送的廣播消息CH＿ELECTED＿M(jìn)SG中.具體流程如圖2所示.

圖2 CBSM算法流程

3 仿真結(jié)果

表1 仿真主要參數(shù)

仿真環(huán)境采用Matlab2008a，仿真算法包括LEACH，RBMC和CBSM.筆者對節(jié)點總數(shù)N＝1 000、區(qū)域半徑為R＝240的場景進(jìn)行了仿真，整個感知區(qū)域分為4個等寬的環(huán)，從最內(nèi)層第1環(huán)到最外層第4環(huán)最優(yōu)簇頭數(shù)目分別為m1＝8，m2＝13，m3＝17，m4＝21.仿真主要參數(shù)見表1.

當(dāng)網(wǎng)絡(luò)中出現(xiàn)節(jié)點死亡時，網(wǎng)絡(luò)性能就會下降，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、數(shù)據(jù)檢測率等都會變差，網(wǎng)絡(luò)開始變得不穩(wěn)定.因此，文中區(qū)別于傳統(tǒng)算法中以所有節(jié)點死亡時間作為網(wǎng)絡(luò)的生命周期，而采用首節(jié)點和一半節(jié)點死亡時間來衡量網(wǎng)絡(luò)的生命周期.

圖3分別是CBSM算法與LEACH算法、RBMC算法存活節(jié)點數(shù)隨網(wǎng)絡(luò)運(yùn)行輪數(shù)的變化曲線.表2是3種算法首節(jié)點和一半節(jié)點死亡時的對應(yīng)輪數(shù).從表2可以看出，以一半節(jié)點死亡時間來衡量網(wǎng)絡(luò)生命周期時，CBSM算法的網(wǎng)絡(luò)生存周期比LEACH算法提高了約414%，比RBMC算法提高了約97%；若以首節(jié)點死亡時間來衡量網(wǎng)絡(luò)生命周期，則CBSM算法分別比LEACH算法和RBMC算法提高了約177%和123%，顯著地延長了網(wǎng)絡(luò)的生命周期.

圖3 節(jié)點存活數(shù)目n＝1 000時剩余節(jié)點數(shù)與輪數(shù)關(guān)系

表2 節(jié)點死亡輪數(shù)對照

圖4顯示了CBSM算法和LEACH算法簇頭數(shù)目變化曲線，SBMC算法的簇頭數(shù)目變化規(guī)律與LEACH算法相同.由圖4可知，CBSM算法簇頭數(shù)目與LEACH算法相比相對較穩(wěn)定.簇頭數(shù)目穩(wěn)定才能保證將區(qū)域內(nèi)節(jié)點采集的信息轉(zhuǎn)發(fā)到基站，保持簇頭數(shù)目的穩(wěn)定在一定程度上提高了整個網(wǎng)絡(luò)的穩(wěn)定性.

圖4 簇頭數(shù)目變化曲線

4 結(jié)語

通過對典型分簇算法LEACH及其改進(jìn)算法RBMC的分析，提出了CBSM算法.CBSM算法將整個網(wǎng)絡(luò)區(qū)域劃分為規(guī)模大小不同的固定小區(qū)，每個小區(qū)作為一個簇，有效地控制了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；同時采用基于節(jié)點剩余能量和節(jié)點位置的代價函數(shù)選舉簇頭，延長了網(wǎng)絡(luò)的生命周期，提高了網(wǎng)絡(luò)的穩(wěn)定性.

［1］ SOHRABI K.Protocols for Self－Organization of a Wireless Sensor Network［J］.IEEE Personal Communications，2000，7（5）：16－27.

［2］ HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－Efficient Communication Protocol for Wireless Micro－Sensor Networks［C］／／Proceedings of IEEE HICSS.Hawaii，USA，2000：223－232.

［3］ SMARAGDAKIS G，MATTA I，BESTAVROS A.SEP：A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks［C］／／Proceedings of SANPA.Boston，Massachusetts，USA，2004：251－261.

［4］ 劉 志，裘正定.基于分環(huán)多跳的無線傳感網(wǎng)分簇路由算法［J］.通信學(xué)報，2008，28（3）：104－113.

［5］ SORO S，HEINZELMAN W R.Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering［C］／／Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium（IPDPS’05）.Denver，Colorado，USA，2005：1－8.

［6］ HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.An Application－Specific Protocol Architecture for Wireless Micro－Sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［7］ 卿 利，朱清新，王明文.異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效成簇算法［J］.軟件學(xué)報，2006，17（3）：481－489.

［8］ BULUSU N，HEIDEMANN J，ESTRIN D.GPS－Less Low－Cost Outdoor Localization for Very Small Devices［J］.Personal Communications，IEEE，2000，7（5）：28－34.

（責(zé)任編輯 向陽潔）

Cluster Structure Stability Based Sub－Ring Algorithm over Multi－Hop Routing

ZHOU Jian－qin，SHI Zhi－yuan，ZHAO Ze－mao
（School of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

The cluster structure stability based sub－ring algorithm over multi－h(huán)op routing（CBSM）is proposed to improve the stability of the wireless sensor network（WSN）and to prolong the lifetime of the network.The main idea of the CBSM is to divide the monitoring area into a number of fixed cells.Then select the cluster head with the residual energy and the nod location in the fixed cell.The simulation results showed that CBSM has a good performance in prolonging the network lifetime and increasing the network stabilization.

fixed partition；clustering routing algorithm；optimal cluster head size；clusters heart；relative distance

TP393

A

10.3969／j.issn.1007－2985.2013.03.004

1007－2985（2013）03－0015－06

無線傳感器網(wǎng)絡(luò)是一種自組織網(wǎng)絡(luò)，隨機(jī)、高密度分布的節(jié)點具有能量有限、片上運(yùn)算能力不足、存儲空間小等特點［1］.其中，節(jié)點的能量對網(wǎng)絡(luò)生命周期的影響最為顯著，這是因為傳感器節(jié)點一般由電池供電，能量有限且不可補(bǔ)充.另外，當(dāng)網(wǎng)絡(luò)中出現(xiàn)節(jié)點死亡時，網(wǎng)絡(luò)性能就會下降，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、數(shù)據(jù)檢測率等都會變差，網(wǎng)絡(luò)開始變得不穩(wěn)定.因此，在確保能量有效性的同時，還要盡量延長網(wǎng)絡(luò)中第1個節(jié)點的死亡時間，以提高整個網(wǎng)絡(luò)的穩(wěn)定性.

傳統(tǒng)路由算法中，分簇路由算法相比于平面路由算法具有更好的能量有效性和可擴(kuò)展性.LEACH（low energy adaptive clustering hierarchy）算法［2］是人們最早提出的分簇算法，其核心思想是讓每個節(jié)點輪流擔(dān)當(dāng)簇頭，將整個網(wǎng)絡(luò)的負(fù)載均勻的分配到每個節(jié)點上.然而LEACH算法只考慮了單跳模型，因此只適合小型WSN（無線傳感器網(wǎng)絡(luò)）.SEP（stable election protocol for clustered heterogeneous wireless sensor networks）算法［3］根據(jù)節(jié)點初始能量的不同，為節(jié)點設(shè)置不同的簇頭選舉概率來均勻能耗，但是SEP算法仍采用類似LEACH的簇頭隨機(jī)選舉策略，從本質(zhì)上說仍然是一個單跳網(wǎng)絡(luò).文獻(xiàn)［4］提出了RBMC（ring based multi－h(huán)op clustering routing algorithm）算法，將檢測區(qū)域分成多個同心圓環(huán)，根據(jù)第1環(huán)能耗最小目標(biāo)和各環(huán)能耗相同原則推導(dǎo)出各環(huán)的最優(yōu)簇頭數(shù)目，外環(huán)簇頭通過內(nèi)環(huán)的簇頭轉(zhuǎn)發(fā)數(shù)據(jù).RBMC算法選擇方法與LEACH算法相同，隨機(jī)動態(tài)地選擇簇頭會造成簇頭數(shù)目高度動態(tài)變化，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不穩(wěn)定，若某輪沒有選出簇頭，則整個網(wǎng)絡(luò)會處于暫時失效的狀態(tài).

為了提高大型網(wǎng)絡(luò)的穩(wěn)定傳輸時間，有效控制網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，筆者提出基于簇結(jié)構(gòu)穩(wěn)定的路由算法CBSM.首先將感知區(qū)域劃分為等寬圓環(huán)，其次按照每環(huán)最優(yōu)簇頭數(shù)目將圓環(huán)分為多個規(guī)模不同的小區(qū)，每個小區(qū)作為一個簇，外環(huán)簇頭通過內(nèi)環(huán)簇頭轉(zhuǎn)發(fā)數(shù)據(jù)，最終建立一個拓?fù)浣Y(jié)構(gòu)穩(wěn)定、能耗均勻的無線傳感網(wǎng)絡(luò).

2012－12－03

浙江省自然科學(xué)基金資助項目（Y1100318；Y1100818）

周建欽（1963－），男，山東巨野人，安徽工業(yè)大學(xué)計算機(jī)學(xué)院教授，碩士，主要從事通信、密碼學(xué)與理論計算機(jī)科學(xué)研究.