文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2015)06-0118-03
0 引言
網(wǎng)絡(luò)中傳感器的數(shù)目過(guò)多,會(huì)使網(wǎng)絡(luò)間通信產(chǎn)生更多的能耗,集中式算法易導(dǎo)致單個(gè)節(jié)點(diǎn)失效[1-2]。因此,無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[3-4]協(xié)議必須含有分布式定位功能。文獻(xiàn)[5]利用自組織方式確保連通性并對(duì)網(wǎng)絡(luò)進(jìn)行重新配置,應(yīng)用于網(wǎng)絡(luò)層或節(jié)點(diǎn)層。然而,每個(gè)節(jié)點(diǎn)都包含在自組織網(wǎng)絡(luò)中時(shí),無(wú)法保證其能量效率[6]。
本文提出一種WSN能效優(yōu)化的自組織位置感知協(xié)議(Energy Efficient Self-organized Location aware Protocol,EESLP),根據(jù)拓?fù)淇刂七M(jìn)行自組織處理,綜合考慮兩個(gè)WSN參數(shù):數(shù)據(jù)包投遞率和能耗,在增加數(shù)據(jù)包傳輸率的同時(shí)降低了能耗。
1 提出的自組織位置感知協(xié)議
本文協(xié)議分四個(gè)步驟進(jìn)行路由選擇,工作流程如圖1所示。
1.1 位置感知結(jié)構(gòu)的構(gòu)建
圖2所示為基于位置感知構(gòu)建的樹(shù)結(jié)構(gòu),其中,黑色節(jié)點(diǎn)表示Sink節(jié)點(diǎn)(根節(jié)點(diǎn)),灰色節(jié)點(diǎn)表示錨主干節(jié)點(diǎn),白色節(jié)點(diǎn)表示葉節(jié)點(diǎn)。位置感知結(jié)構(gòu)構(gòu)建算法如算法1所示。
算法1:位置感知結(jié)構(gòu)構(gòu)建算法
輸入:含有V個(gè)頂點(diǎn)(V←v1,v2,…,vn)和E條邊的非連通圖G。
輸出:通過(guò)錨節(jié)點(diǎn)進(jìn)行完全連接的樹(shù)結(jié)構(gòu)。
(1)在圖G選取根頂點(diǎn)VR,即VR∈G。//VR是Sink節(jié)點(diǎn)
(2)添加連接VR和vi以及節(jié)點(diǎn)vi和vj的邊ei。//i,j=1,2,3…
(3)若vi和vj是VR的兩跳距離節(jié)點(diǎn),則執(zhí)行步驟(4)
(4)檢測(cè)C(連通性)。//利用G圖中的兩個(gè)未連接鄰居節(jié)點(diǎn)將vi和vj連接
(5)選取vabi和vabj作為第一層主干錨節(jié)點(diǎn),命名為Vab1和Vab2。//Vab表示主干錨節(jié)點(diǎn)
(6)持續(xù)步驟(3)~(5),直到圖G中的所有節(jié)點(diǎn)都連接
(7)通過(guò)Vabi和Vabj將位置信息告知VR
(8)否則
(9)運(yùn)行步驟(2)
(10)結(jié)束
1.2 用于結(jié)構(gòu)維護(hù)的拓?fù)淇刂?/strong>
利用拓?fù)淇刂凭S護(hù)結(jié)構(gòu)貫穿整個(gè)過(guò)程,通常通過(guò)減少或簡(jiǎn)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)進(jìn)行節(jié)能,同時(shí)維持網(wǎng)絡(luò)的一些重要特性(如連通性和覆蓋范圍等)[7]。拓?fù)淇刂坪途S護(hù)算法如算法2描述。
算法2:拓?fù)淇刂坪徒Y(jié)構(gòu)維護(hù)算法
輸入:含有V個(gè)頂點(diǎn)(V←v1,v2,…,vn)和E條邊的未連接圖G。
輸出:通過(guò)錨節(jié)點(diǎn)進(jìn)行完全連接的樹(shù)結(jié)構(gòu)。
階段一:利用拓?fù)淇刂七M(jìn)行拓?fù)浣Y(jié)構(gòu)簡(jiǎn)化(連通性和覆蓋范圍)
(1)當(dāng)V中節(jié)點(diǎn)v(葉節(jié)點(diǎn))的能量減少或改變位置時(shí)。//節(jié)點(diǎn)能量耗盡或節(jié)點(diǎn)處于運(yùn)動(dòng)過(guò)程中
(2)vai←vi。狀態(tài)的改變指向錨主干
(3)vi←vabi←VR。//連通維護(hù)層級(jí)VR,vbi和v,其中v與新錨點(diǎn)vbi連接
(4)若vbi的一跳鄰居節(jié)點(diǎn)中含有一跳未連接的路徑,將vbi添加到vb上
(5)更新G中所有的由vi到vabi的連接
(6)樹(shù)(T)結(jié)構(gòu)維護(hù)
階段二:拓?fù)浣Y(jié)構(gòu)維護(hù)階段。
(7)使G含有vi,vab和VR
(8)若P(vi≠vab≠VR)能量不等
(9)則從G移出vi,當(dāng)需要時(shí)恢復(fù)vi
(10)在G中利用VR維護(hù)樹(shù)結(jié)構(gòu)
1.3 節(jié)能機(jī)制
利用位置模型對(duì)網(wǎng)絡(luò)進(jìn)行建模,將網(wǎng)絡(luò)拓?fù)渥鳛闃?gòu)建結(jié)構(gòu)的關(guān)鍵參數(shù),能量效率如圖3所示,負(fù)載均衡算法如算法3所示。
算法3:負(fù)載平衡算法
輸入:無(wú)向圖G=(V,E)。//V,E分別表示頂點(diǎn)和邊的集合。
輸出:一個(gè)連接網(wǎng)格結(jié)構(gòu)L表示圖G的子集。
(1)構(gòu)建局部網(wǎng)格結(jié)構(gòu)ln←{V,E}。//在其覆蓋區(qū)域內(nèi)至少含有2個(gè)未連接的鄰居節(jié)點(diǎn)
(2)在ln∈L中構(gòu)建1個(gè)一維的網(wǎng)格集合
(3)L(v)∈{G},這里L(fēng)≥2,3,4,…。//v表示一個(gè)頂點(diǎn)
(4)在集合L中尋找一個(gè)子集合A用于更替路由,如l1,l2,…,ln∈V
(5)若l1,l2為更替路由虛擬節(jié)點(diǎn)。//節(jié)點(diǎn)度l1,l2≥1或2
(6)則將葉節(jié)點(diǎn)n與L或l連接
(7)向局部網(wǎng)絡(luò)添加節(jié)點(diǎn)Ln←L∪l∪n
(8)當(dāng)L(v)改變其位置時(shí)。//v,u是L(局部結(jié)構(gòu))中的頂點(diǎn)
(9)l(u)←L(v)。//通過(guò)′l′維護(hù)連接′L′,l是L的子集
(10)只有當(dāng)l一跳連接u和v,則增加v,u
(11)類(lèi)似的,添加一跳l1,l2,…,ln到L的其他節(jié)點(diǎn)
(12)(l,n)←更新i。//i為信息狀態(tài)
(13)若l1在一跳中不可利用或不在傳輸范圍內(nèi)。//僅用于較小傳輸范圍
(14)n←l。//葉節(jié)點(diǎn)(n)變成虛擬節(jié)點(diǎn)
1.4 自組織
利用自組織方式[8]降低節(jié)點(diǎn)或網(wǎng)絡(luò)中的消息復(fù)雜度,為避免碰撞、競(jìng)爭(zhēng)和連接失敗等問(wèn)題,通過(guò)重建和位置結(jié)構(gòu)的拓?fù)溥^(guò)程獲得自組織,利用分布式定位算法實(shí)現(xiàn)位置結(jié)構(gòu)的拓?fù)溥^(guò)程。若一個(gè)節(jié)點(diǎn)希望進(jìn)入任何一個(gè)工作區(qū)域,則會(huì)對(duì)它的服務(wù)進(jìn)行分層限制,并產(chǎn)生支持每個(gè)節(jié)點(diǎn)的平面路由。在真實(shí)的數(shù)據(jù)傳輸過(guò)程中(如網(wǎng)絡(luò)電話),僅有平面路由是不行的。與此同時(shí),在一個(gè)分層系統(tǒng)中,將實(shí)時(shí)傳輸設(shè)置為高優(yōu)先級(jí),并將節(jié)點(diǎn)連接到低擁堵的區(qū)域。為了減少路由和控制開(kāi)銷(xiāo),允許中間節(jié)點(diǎn)或中繼節(jié)點(diǎn)處理其他節(jié)點(diǎn)的擁堵情況。自組織算法如算法4所示。
算法4:EESLP中的自組織算法
(1)算法在G中的每個(gè)WSN上執(zhí)行;L∈G,L為位置結(jié)構(gòu)
(2)用i表示整數(shù),w,r∈Wi;//Wi為位置結(jié)構(gòu)節(jié)點(diǎn)集合,w為Wi中元素,r為中繼節(jié)點(diǎn)
(3)執(zhí)行自私行為,調(diào)整節(jié)點(diǎn)到其最初的位置或維護(hù)路由進(jìn)程
(4)if將wi變?yōu)閣i+1 or將ri變?yōu)閞i+1,then
(5)在G中尋找所有可能執(zhí)行自私行為的自組織節(jié)點(diǎn)
(6)if w=w(i),then
(7) if ′i′是奇數(shù),then w支撐奇數(shù)連接(最小度)
(8) else if ′i′為偶數(shù),將連接調(diào)整到i+1個(gè)ri節(jié)點(diǎn)
(9) end
(10)else 為連通性選取新的wi
(11)end
2 實(shí)驗(yàn)
在移動(dòng)場(chǎng)景和穩(wěn)定場(chǎng)景下對(duì)本文協(xié)議進(jìn)行了仿真實(shí)驗(yàn)和分析。
2.1 實(shí)驗(yàn)設(shè)置
仿真中,接收功率設(shè)置為0.1 W,傳輸功率設(shè)置為0.281 4 W。利用NS2仿真器構(gòu)建含有200個(gè)節(jié)點(diǎn)、大小為1 000 m×1 000 m的WSN區(qū)域,聞?dòng)嶉g隔為0.90 s,采用隨機(jī)位點(diǎn)模型。所有節(jié)點(diǎn)的初始能量為0.25 J,節(jié)點(diǎn)的傳輸范圍為10 m~50 m,仿真持續(xù)時(shí)間為120 s。在第一種場(chǎng)景中,所有節(jié)點(diǎn)都是固定的,并且按序生成10個(gè)UDP會(huì)話,每個(gè)會(huì)話傳輸50個(gè)恒定比特率(CBR)數(shù)據(jù)包。在初始階段,所有節(jié)點(diǎn)都是黑色的,擁有紅色節(jié)點(diǎn)的度為5;用黃色表示運(yùn)動(dòng)節(jié)點(diǎn)。在移動(dòng)體系結(jié)構(gòu)中,設(shè)置節(jié)點(diǎn)的移動(dòng)速率為1 m/s。利用穩(wěn)定能效自組織位置感知協(xié)議(Stable Energy Efficient Self-organized Location aware Protocol,SEESLP)表示穩(wěn)定性分析,移動(dòng)能效自組織位置感知協(xié)議(Mobile Energy Efficient Self-organized Location aware Protocol,MEESLP)表示移動(dòng)場(chǎng)景分析,另外,每個(gè)場(chǎng)景下設(shè)置2種覆蓋區(qū)域范圍,I和II分別表示25 m和50 m的覆蓋區(qū)域。
2.2 結(jié)果分析
由于網(wǎng)絡(luò)是利用標(biāo)記策略形成,因此作為關(guān)鍵因素的位置路由成為性能比較的重點(diǎn)。在相同的參數(shù)設(shè)置下,隨機(jī)生成10個(gè)連接的UDGs,計(jì)算每個(gè)圖的LS以及平均LS尺寸,LS表示位置結(jié)構(gòu)中用于維護(hù)連通性所需的節(jié)點(diǎn)個(gè)數(shù),結(jié)果如圖4所示。由圖4可知,SEESLP-II策略?xún)H需要8%的節(jié)點(diǎn)去維護(hù)連通性。根據(jù)鄰近Sink節(jié)點(diǎn)識(shí)別機(jī)制,位置結(jié)構(gòu)中僅需12個(gè)節(jié)點(diǎn)連接Sink節(jié)點(diǎn)與源節(jié)點(diǎn)。另一方面,MEESLP-I需要25%的節(jié)點(diǎn)進(jìn)行移動(dòng)維護(hù),這是因?yàn)樵谝苿?dòng)場(chǎng)景下,具有高的節(jié)點(diǎn)密度和節(jié)點(diǎn)移動(dòng)性,節(jié)點(diǎn)之間需要交換更多的控制負(fù)載。同時(shí)還可以看出,若網(wǎng)絡(luò)是稀疏的,網(wǎng)絡(luò)中的大多數(shù)節(jié)點(diǎn)將會(huì)被一個(gè)位置結(jié)構(gòu)包含,這與高或低的節(jié)點(diǎn)度策略無(wú)關(guān)。若網(wǎng)絡(luò)變得稠密,利用高節(jié)點(diǎn)度減小EESLP的尺寸。因此,最高節(jié)點(diǎn)度策略?xún)?yōu)于最小節(jié)點(diǎn)度策略。
傳輸范圍分析是基于不同傳輸范圍內(nèi)所需的中間節(jié)點(diǎn)的個(gè)數(shù)。不同場(chǎng)景下,傳輸范圍在10 m~50 m內(nèi)變化時(shí),控制節(jié)點(diǎn)個(gè)數(shù),結(jié)果如圖5所示??梢钥闯觯琒EESLP中,當(dāng)傳輸范圍為10 m時(shí),連通性?xún)H需30個(gè)控制節(jié)點(diǎn),隨著傳輸范圍的增加,所需的控制節(jié)點(diǎn)個(gè)數(shù)相應(yīng)減少,當(dāng)傳輸范圍為50 m時(shí),相應(yīng)的控制節(jié)點(diǎn)個(gè)數(shù)為11。由于結(jié)構(gòu)的位置性,MEESLP需要近50%的節(jié)點(diǎn)維護(hù)連通性。此外,隨著傳輸范圍由40 m增加到50 m,兩種方法的LS尺寸都減少,隨著傳輸范圍的進(jìn)一步增加,這兩種方法的尺寸會(huì)越來(lái)越接近。
平均節(jié)點(diǎn)度分析中,評(píng)估了節(jié)能方法的可擴(kuò)展性,如圖6所示,網(wǎng)絡(luò)的密度限制為200個(gè)節(jié)點(diǎn)。從圖中可知,SEESLP-II僅需4個(gè)中繼節(jié)點(diǎn)。由于當(dāng)一個(gè)支配者的節(jié)點(diǎn)級(jí)別增加,它就不能連接所有的節(jié)點(diǎn),因此與傳輸范圍分析相比,節(jié)點(diǎn)級(jí)別分析需要更大量的中間節(jié)點(diǎn)。
圖7顯示了數(shù)據(jù)包投遞率的比較。一個(gè)數(shù)據(jù)包的大小在16 bit到128 bit之間變化,利用本文協(xié)議傳輸數(shù)據(jù)包并對(duì)包投遞率進(jìn)行分析。在WSN網(wǎng)絡(luò)中存在3種會(huì)影響PDR的情況:(1)節(jié)點(diǎn)發(fā)送功率變化;(2)節(jié)點(diǎn)數(shù)量變化;(3)網(wǎng)絡(luò)大小變化。
2.3 性能比較
將本文協(xié)議與文獻(xiàn)[5]、文獻(xiàn)[7]和文獻(xiàn)[8]提出的協(xié)議進(jìn)行比較,結(jié)果如圖7(a)所示。從圖中可以看出,本文協(xié)議具有最優(yōu)的數(shù)據(jù)包投遞率。
本文協(xié)議的一個(gè)重要衡量指標(biāo)是能量分析。在初始階段,所有節(jié)點(diǎn)的能量設(shè)置為0.25 J,將0.1 J設(shè)置為能量閾值。將本文協(xié)議與文獻(xiàn)[5]、文獻(xiàn)[7]和文獻(xiàn)[8]提出的協(xié)議進(jìn)行比較,結(jié)果如圖7(b)所示。從圖7(b)可以看出,本文協(xié)議在120 s后網(wǎng)絡(luò)節(jié)點(diǎn)平均能量仍然能夠保持70%,很好地均衡了網(wǎng)絡(luò)節(jié)點(diǎn)能量,提高了網(wǎng)絡(luò)壽命。
3 結(jié)束語(yǔ)
本文提出了一種利用能效優(yōu)化的自組織位置感知協(xié)議,根據(jù)主干錨節(jié)點(diǎn)的位置感知將網(wǎng)絡(luò)構(gòu)建成樹(shù)結(jié)構(gòu),利用拓?fù)淇刂苾?yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)維持網(wǎng)絡(luò)的連通性和覆蓋范圍。同時(shí)在路徑選擇過(guò)程中加入節(jié)能機(jī)制,從而均衡網(wǎng)絡(luò)負(fù)載。在運(yùn)行過(guò)程中,利用自組織方式最小化消息傳輸和接收次數(shù),降低消息復(fù)雜度,減少協(xié)議開(kāi)銷(xiāo)。未來(lái)研究將會(huì)考慮傳感器網(wǎng)絡(luò)快速運(yùn)動(dòng)情況。
參考文獻(xiàn)
[1] ZENG Y,CAO J,HONG J,et al.Secure localization and location verification in wireless sensor networks: a survey[J].The Journal of Supercomputing,2013,64(3):685-701.
[2] YU G,YU F.A localization algorithm for mobile wireless sensor networks[C].Integration Technology,2007.ICIT′07.IEEE International Conference on.IEEE,2007:623-627.
[3] CUZZOCREA A,PAPADIMITRIOU A,KATSAROS D,et al.Edge betweenness centrality:A novel algorithm for QoS-based topology control over wireless sensor networks[J].Journal of Network and Computer Applications,2012,35(4):1210-1217.
[4] 趙雁航,錢(qián)志鴻,尚小航,等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報(bào),2013,34(9):105-114.
[5] VECCHIO M,López-Valcarce R,MARCELLONI F.A two-objective evolutionary approach based on topological constraints for node localization in wireless sensor networks[J].Applied Soft Computing,2012,12(7):1891-1901.
[6] GENTILE C,ALSINDI N,RAULEFS R,et al.Cooperative localization in wireless sensor networks:distributed algorithms[C].Geolocation Techniques.Springer New York,2013:187-211.
[7] 康一梅,李志軍,胡江,等.一種低能耗層次型無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].自動(dòng)化學(xué)報(bào),2010,36(4):543-549.
[8] LUO X,YU H,WANG X.Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks[J].International Journal of Systems Science,2013,44(10):1857-1866.