移動(dòng)無線傳感網(wǎng)絡(luò)簇頭多跳路由協(xié)議

1、移動(dòng)無線傳感網(wǎng)絡(luò)簇頭多跳路由協(xié)議作者：張緒昌謝志軍何加銘 來源：移動(dòng)通信2013年笫06期【摘要】隨著無線傳感器網(wǎng)絡(luò)在移動(dòng)環(huán)境小廣泛應(yīng)用，移動(dòng)環(huán)境下降低能耗成了傳感網(wǎng) 絡(luò)研究的熱點(diǎn)。通過研究移動(dòng)環(huán)境下的各種路宙協(xié)議，并結(jié)合leach協(xié)議自身存在的問題， 提出了一種支持移動(dòng)的簇頭多跳的路由算法。該協(xié)議充分考慮了剩余能暈、速度和距離，以及 簇頭選取和簇的構(gòu)成方法，提出新的權(quán)值函數(shù)，從而有效地支持節(jié)點(diǎn)移動(dòng)。仿真結(jié)果表明，該 協(xié)議有效地均衡了節(jié)點(diǎn)能耗，提高了能量利用率，延長了網(wǎng)絡(luò)壽命?！娟P(guān)鍵詞】無線傳感網(wǎng)絡(luò)分簇多跳路曲算法移動(dòng)性1引言傳感器在計(jì)算和無線通訊中廣泛使用，如監(jiān)測外部環(huán)境，把感知的數(shù)據(jù)轉(zhuǎn)化為

2、用戶可以理 解的信息。傳感網(wǎng)絡(luò)的應(yīng)用是冃前國際科學(xué)研究的熱點(diǎn)。隨著社會(huì)的發(fā)展，在很多的移動(dòng)壞境 應(yīng)用了無限傳感器，如海洋的監(jiān)測、移動(dòng)車輛的監(jiān)測、動(dòng)物的監(jiān)測等，因此研究移動(dòng)環(huán)境下的 無線傳感器網(wǎng)絡(luò)越來越重要1 -2。傳感器網(wǎng)絡(luò)的移動(dòng)性帶來了許多問題。如傳感器節(jié)點(diǎn)在成功部署之后由于節(jié)點(diǎn)的移動(dòng)隨時(shí) 變換位置，很容易造成拓?fù)涞淖兓煌ㄐ沛溌方⒅?，?jié)點(diǎn)移動(dòng)很容易偏離最初的位置，從 而導(dǎo)致連接斷裂、路由中斷；節(jié)點(diǎn)移動(dòng)造成數(shù)據(jù)延遲發(fā)送；節(jié)點(diǎn)的移動(dòng)造成路山建立的頻率增 大，從而増大能量的消耗，縮短了網(wǎng)絡(luò)生存吋間。因此針対移動(dòng)環(huán)境設(shè)計(jì)支持移動(dòng)性的路由i辦 議十分必要。基于分簇的路由協(xié)議有很多。leach3的

3、成簇思想貫穿于其后發(fā)展出的很多分簇路由協(xié) 議屮，如teen4、pegasis5、apteen都基于分簇的路由協(xié)議，但在移動(dòng)性的支持上 存在不足，尤其當(dāng)網(wǎng)絡(luò)規(guī)模增人時(shí)，缺陷就更加明顯。m-leach是慕于leach提出的支 持簇頭和成員節(jié)點(diǎn)的移動(dòng)協(xié)議，簇頭選取時(shí)考慮了節(jié)點(diǎn)剩余能量、位置及節(jié)點(diǎn)的移動(dòng)速率，但 沒有在簇的建立階段解決移動(dòng)性問題。emhr8算法是簇頭在數(shù)據(jù)傳輸時(shí)對(duì)以通過多跳傳輸， 根據(jù)權(quán)值確定下一跳簇頭，這樣emhr協(xié)議在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中平衡負(fù)載和降低簇頭能量消 耗，此協(xié)議主要是針對(duì)靜態(tài)網(wǎng)絡(luò)。分簇技術(shù)可以避免感知節(jié)點(diǎn)之間的信息傳輸，通過簇頭數(shù)據(jù)融合，減少數(shù)據(jù)冗余，減少發(fā) 送數(shù)據(jù)量，降低能

4、耗，更好地支持移動(dòng)性。多跳傳輸技術(shù)是動(dòng)態(tài)自組織，利用網(wǎng)絡(luò)中的節(jié)點(diǎn)動(dòng) 態(tài)建立和維持網(wǎng)絡(luò)連接。ft于多跳技術(shù)的獨(dú)特性，無線傳感網(wǎng)絡(luò)多跳技術(shù)得到了極人的關(guān)注， 大量信息表明多跳路由協(xié)議的能耗遠(yuǎn)低于單跳路由協(xié)議。針對(duì)現(xiàn)有分簇路由屮存在的缺陷，木 文提出新的支持移動(dòng)的簇頭多跳路由算法，以降低能耗。2 em-chmr 算法基于leach-m算法，在感知節(jié)點(diǎn)移動(dòng)且基站（bs）不移動(dòng)的環(huán)境下，根據(jù)節(jié)點(diǎn)的移動(dòng) 信息進(jìn)行分簇，分簇成功之后建立高效的多跳路徑，筆者提出能有效地支持移動(dòng)性的簇頭多跳 路由策略（emchmr, energy-efficient mobile cluster head multi-hops

5、 routing protocol）。此 路由策略中，簇首向基站傳輸數(shù)據(jù)引入了多跳路山機(jī)制，讓距基站較近的簇首適當(dāng)承擔(dān)一些數(shù) 據(jù)中繼轉(zhuǎn)發(fā)任務(wù)，把直接長距離通信變成間接的多次短距離通信，在支持移動(dòng)下保證轉(zhuǎn)發(fā)簇首 有充分的能量來進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。2分簇的模型簇頭多跳的簡單模型如圖1,模世中距離bs較遠(yuǎn)的簇頭可以通過建立多跳路徑與bs通 信，這樣可以降低自身的能量消耗。同時(shí)距離bs較近的簇頭不需要再進(jìn)行多跳，對(duì)以肖接與 bs進(jìn)行通信。模型中感知肖點(diǎn)和簇頭都可以進(jìn)行移動(dòng)，但是bs是|占i定位置不移動(dòng)；每個(gè)節(jié)點(diǎn) 的移動(dòng)速度大小都限制在-定范忸內(nèi)；節(jié)點(diǎn)同構(gòu)，且初始能暈相同；傳感器節(jié)點(diǎn)得到的信息， 可以使用gp

6、s或其他位置檢測方案；傳感器節(jié)點(diǎn)的發(fā)射功率可以進(jìn)行調(diào)節(jié)。路由算法屮利用文獻(xiàn)9提出的能屋消耗模型，節(jié)點(diǎn)發(fā)射kbit數(shù)據(jù)到距離為d的位置消耗的 能量為：其屮，eelec表示發(fā)端電路運(yùn)算和處理每比特?cái)?shù)據(jù)的能耗；£fs和wmp為放人器的系數(shù)；do 為臨界距離。2.2簇頭的選取簇頭選取算法是基于m-leach協(xié)議提出的，網(wǎng)絡(luò)模型是一個(gè)均勻的網(wǎng)絡(luò)，簇頭的數(shù)量確 定方式與m-leach相同。根據(jù)簇頭數(shù)量把整個(gè)區(qū)域劃分為子區(qū)域，然后為每個(gè)區(qū)域選取簇 頭。首先按照剩余能量利用閾值eselect進(jìn)行篩選，避免節(jié)點(diǎn)剩余能量不足造成早死現(xiàn)象。為 了讓簇頭均勻分布并對(duì)蔡個(gè)傳感網(wǎng)絡(luò)實(shí)現(xiàn)完全覆蓋，把整個(gè)區(qū)域分成m

7、個(gè)子區(qū)域，在每一個(gè) 子區(qū)域屮選取一個(gè)簇頭。假設(shè)第j子區(qū)域節(jié)點(diǎn)數(shù)nj,每個(gè)節(jié)點(diǎn)坐標(biāo)為（xi, yj）,速度為vi。 簇頭的最佳位置so計(jì)算方式如下：移動(dòng)方向用bi （oo<0i<18oo）表示，意為節(jié)點(diǎn)i的移動(dòng)方向和連接節(jié)點(diǎn)指向最佳位置的直 線形成的夾角（速度和肖線的最小夾角）。最佳選擇則是節(jié)點(diǎn)移動(dòng)方向是so,即夾角越小越 好。角度則是處理后的角度，其中ot是角度閾值。如果簇頭移動(dòng)速度過快則容易造成簇的破壞，移動(dòng)速度慢則適合整個(gè)網(wǎng)絡(luò)的移動(dòng)速度。式（4）表示節(jié)點(diǎn)i處理后的速度，其中vt是速度閾值，vi為節(jié)點(diǎn)i的速度。節(jié)點(diǎn)i為簇頭的代價(jià)函數(shù)為:由式(5)看到，、和變小時(shí)值也變小，則是節(jié)點(diǎn)

8、i的速度因了，因此最小的節(jié)點(diǎn)為簇頭 扱理想的節(jié)，若存在多個(gè)節(jié)點(diǎn)，取最小值。2.3簇的形成簇的形成階段，就是在感知節(jié)點(diǎn)選擇簇頭鍵入，并在其中形成簇。簇頭和感知節(jié)點(diǎn)的移動(dòng) 使得節(jié)點(diǎn)與簇頭位置關(guān)系的變化很難計(jì)算。為了降低復(fù)雜性，把速度大小和速度方向一起分 析，利用速度和角度得到速度因子。莫屮，vi根據(jù)閾值計(jì)算，山是感知節(jié)點(diǎn)移動(dòng)方向與連接感知節(jié)點(diǎn)、簇頭間直線所形成的夾 角，00是簇頭移動(dòng)方向和連接簇頭、感知節(jié)點(diǎn)的肖線所形成的夾角?？梢钥磳?，移動(dòng)因了不 是兩個(gè)速度的欠量和，而是要考慮到兩個(gè)速度的移動(dòng)方向變化，方能夠簡單高效地對(duì)節(jié)點(diǎn)移動(dòng) 性進(jìn)行評(píng)估?；趀ecs10協(xié)議，木文提出新的通信代價(jià)函數(shù)：其中e=

9、en_init/en_current, vv是貝體環(huán)境決定的權(quán)值，chi是區(qū)域i的簇頭，bs為基詁， d是距離，f是兩者之間的通信代價(jià)，ex為期望。si為感知節(jié)點(diǎn)。cost (i, j)表示成員節(jié)點(diǎn)i 到簇頭j的通信代價(jià)，在簇的形成過程中，每個(gè)成員節(jié)點(diǎn)選取通信代價(jià)最小的簇頭加入簇區(qū) 域。2.4多跳路徑建立在數(shù)據(jù)傳輸中選擇下一跳的簇頭，對(duì)簇頭能暈消耗有重要的影響。如果bs在簇頭傳輸?shù)?有效范圍內(nèi)，簇頭將直接與bs進(jìn)行通信，否則通過其他簇頭進(jìn)行多跳傳輸。為了多跳能量消耗，計(jì)算通過簇頭跳一次的情況，即從簇頭i到j(luò)再到bs。設(shè)簇頭i和j 的距離為d (i, j) , j和bs的距離為d (j, s)

10、o根據(jù)無線通信能屋消耗模型，總的能暈消耗 模型et為：可看出能量消耗的影響因素為d (i, j)和d (j, s),所以，簇頭i發(fā)送消息經(jīng)過n個(gè)簇 頭到bs的能量消耗為：式(10)充分體現(xiàn)了距離對(duì)簇頭能量的消耗的影響，i次i此對(duì)用距離的平方和作為權(quán)值函數(shù) 的一個(gè)重要因索。由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)是移動(dòng)狀態(tài)，尤其在簇頭多跳網(wǎng)絡(luò)中，簇頭的移動(dòng)很容易対多 跳路徑造成破壞，因此在多跳路徑建立過程中要選取一條比穩(wěn)定il受速度影響較少的路徑。在 簇頭多跳路徑中簇頭的移動(dòng)可以縮短榕個(gè)路徑的距離，也有對(duì)能使得路徑遭到破壞。由圖2看到簇頭ho經(jīng)過(hl, h2, h3)到達(dá)基站bs, (si, s2, s3)分

11、別為簇頭到 直線os的距離，0為h3移動(dòng)方向與s3形成的角度。在多跳路徑中最好的效果是三個(gè)簇頭向 os移動(dòng)，并且三個(gè)簇頭和os的距離波動(dòng)不要太大，因?yàn)椴▌?dòng)過大會(huì)造成傳輸距離加大。因 此要(0, si, s2, s3, 0)(前后兩個(gè)0分為h0和bs到os的距離)的方差來衡星節(jié)點(diǎn) 的波動(dòng)，它們的期望衡量嚴(yán)重偏離os的大小。由丁節(jié)點(diǎn)的移動(dòng)造成簇頭位置的不斷變化，為 了較好地反應(yīng)簇頭的移動(dòng)，要充分考慮簇頭節(jié)點(diǎn)的移動(dòng)速度大小和方向。si在os左而值為 正，右血值為負(fù)。角度則是指向os的銳角，反向?yàn)殁g角。當(dāng)多跳經(jīng)過簇頭數(shù)為n時(shí)，計(jì)算 (si+vitcos0)的期望:計(jì)算對(duì)應(yīng)方差：其中t是根據(jù)輪到吋間設(shè)定

12、的值，設(shè)為半個(gè)輪吋間。則新的權(quán)值函數(shù)如下：ei residual是簇頭i的剩余能量，ei init是初始化能量。為了控制c和es值極端情況(只 等于0),約束如下：在簇頭選取成功時(shí)，向周圍廣播信息通知普通廿點(diǎn)，每一個(gè)簇頭會(huì)接收到周圍相鄰的信 息，信息包括id、移動(dòng)信息、剩余能量等。每個(gè)簇頭把周圍的信息進(jìn)行存儲(chǔ)，然后根據(jù)收集 的鄰居節(jié)點(diǎn)找出到bs的所有路徑，利用權(quán)值函數(shù)(11)進(jìn)行計(jì)算，權(quán)值最小的路徑的第二個(gè) 簇頭作為卜一跳節(jié)點(diǎn)。利用此算法，簇頭都可以找到卜-一跳節(jié)點(diǎn)。如果某簇頭能量不足作為多 跳節(jié)點(diǎn)時(shí)，就向周閘發(fā)送取消作為多跳節(jié)點(diǎn)的信息，周圍簇頭把該節(jié)點(diǎn)記錄信息取消，從新選 取下跳節(jié)點(diǎn)。3實(shí)驗(yàn)

13、結(jié)呆實(shí)驗(yàn)無線傳感器網(wǎng)絡(luò)有100個(gè)感知節(jié)點(diǎn)組成，分布在100m* 100m的區(qū)域中，某站bs隨機(jī) 放在此區(qū)域屮。速度范圍為(0, 2) m/s,速度閾值為0.3m/s,角度閾值為10o,方差和期望 的閾值為1,相關(guān)參數(shù)如表1：圖3表示隨著時(shí)間延長，感知節(jié)點(diǎn)逐漸出現(xiàn)了死亡現(xiàn)象，em-chmr協(xié)議的死亡節(jié)點(diǎn)出現(xiàn) 較晚，兩種節(jié)點(diǎn)死亡數(shù)量在300s z后大量出現(xiàn)。在600s z后新協(xié)議的存活節(jié)點(diǎn)數(shù)量明顯高于 m-leach協(xié)議的節(jié)點(diǎn)存活數(shù)量，表明簇頭多跳網(wǎng)絡(luò)較好地均衡了簇之間的能量，降低了感知 節(jié)點(diǎn)的死亡數(shù)量。圖4展示了能量消耗，可以明顯看iii m-leach能量已經(jīng)消耗遠(yuǎn)高于em-chmr,在900

14、s 時(shí)m-leach能量消耗完畢，而em-chmr還冇能量剩余，從而有效地延長了網(wǎng)絡(luò)生存時(shí) 間。能量消耗和存活節(jié)點(diǎn)數(shù)量的變化充分體現(xiàn)支持移動(dòng)的簇頭多跳路由協(xié)議能夠較好支持移 動(dòng)，平衡節(jié)點(diǎn)能量，降低能耗，延長格個(gè)網(wǎng)絡(luò)的存活時(shí)間。4結(jié)束語本文針對(duì)無線傳感器網(wǎng)絡(luò)的移動(dòng)性，基于leach提出了 em-chmr路由算法，保持了按 輪進(jìn)行分簇，對(duì)簇頭節(jié)點(diǎn)采用了多跳算法，提出了信息權(quán)值函數(shù)及建立多跳路徑算法。仿真結(jié) 果證明該方案支持移動(dòng)的簇頭多跳路由策略，使得能量消耗均衡地分布在各節(jié)點(diǎn)上，保證了數(shù) 據(jù)盡快地傳輸?shù)交荆瑥浹a(bǔ)單跳的不足，從而使網(wǎng)絡(luò)壽命得到延長。支持移動(dòng)的簇頭多跳路由 協(xié)議的維護(hù)機(jī)制對(duì)簇和路徑的

15、牛存時(shí)間有很大的影響，因此，為了使移動(dòng)傳感網(wǎng)絡(luò)中更好地降 低能耗，還需要在路由維護(hù)機(jī)制方面展開更深一步的研究。參考文獻(xiàn)：1 akyildiz l f, su weilian, circi e. a survey on sensor neorksj. ieeecommunications magazine, 2002, 40 (8) :102-114.2 yick j, mukherjee b, ghosal d. wireless sensor network surveyj. computer networks, 2008, 52 (12) : 2292-2330.3 heinzelman

16、w r , chandrakasan a, balakrishnan h. energy-efficientcommunication protocol for wireless micro-sensor networksc. proceedings of the 33rd annual hawaii international conference on system sciences (hicss) , maui, hi, 2000：1-10.4 manjeshwar a, agrawal d p. teen： a routing protocol for enhanced efficie

17、ncy in wireless sensor networksc. parallel and distributed processing symposium, proceedings 15th international, 2001 ： 2009-2015.5 lindsey s, raghavendra c s. pegasis: power efficient gathering in sensorinformation systemsc. aerospace conference proceedings, 2002：1125-1130.6 manjeshwar a, agrawal d

18、 p. apteen： a hybrid protocol for efficient routingand comprehensive information retrieval in wireless sensor networks. parallel and distributed processing symposiumc. proceedings of the international, 2002：195-202.7 lan tien nguyen, defagox, beu ran r, et al. an energy efficient routing scheme for mobile wireless sensor networksc. proceedings of the 2008 ieee international symposium on wireless communication systems (iswcs) , 2008： 568-572.8 huang wen wen, peng ya li, wen jia, et al. e