《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 利用能效優(yōu)化的WSN自組織位置感知協(xié)議
利用能效優(yōu)化的WSN自組織位置感知協(xié)議
2015年電子技術(shù)應(yīng)用第6期
陳孝蓮1,周 琦1,楊小偉2
1.江蘇省電力公司無(wú)錫供電公司,江蘇 無(wú)錫214000) 2.南京工程學(xué)院 通信工程學(xué)院,江蘇 南京211167
摘要: 針對(duì)無(wú)線傳感器網(wǎng)絡(luò)存在能耗和投遞率等約束問(wèn)題,提出了一種利用能效優(yōu)化的自組織位置感知協(xié)議(EESLP)。首先,根據(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ò)的連通性和覆蓋范圍;接著,在路徑選擇過(guò)程中加入節(jié)能機(jī)制,均衡網(wǎng)絡(luò)負(fù)載;最后,利用自組織方式最小化消息傳輸和接收次數(shù),降低消息復(fù)雜度,減少協(xié)議開(kāi)銷(xiāo)。仿真實(shí)驗(yàn)結(jié)果表明,該協(xié)議具有良好的能量效率,相比其他幾種能量感知協(xié)議,該協(xié)議具有更高的包投遞率和更低的能耗,有效延長(zhǎng)了網(wǎng)絡(luò)壽命。
中圖分類(lèi)號(hào): TP393
文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2015)06-0118-03
A location aware routing protocol by using energy efficient optimization in WSN
Chen Xiaolian1,Zhou Qi1,Yang Xiaowei2
1.Wuxi Power Supply Company,Jiangsu Electric Power Company,Wuxi 214000,China; 2.College of Communication Engineering,Nanjing Institute of Technology,Nanjing 211167,China
Abstract: In order to solve the energy consumption and delivery ratio constraint problem in wireless sensor network,an energy efficient self-organized location aware protocol is proposed. Firstly, according to the location aware of backbone anchor nodes construction network into a tree structure; secondly, using topology control optimize the network topology to maintain network connectivity and coverage; then, adding energy saving mechanism in the path selection process, balance the network load; using self-organizing minimize the number of message transmit and receive to reduce the message complexity and protocol overhead. Simulation results show that, the protocol has good energy efficiency, and it has higher packet delivery ratio and lower energy consumption, which indicates that it has effectively prolonged the network lifetime.
Key words : wireless sensor network;location aware;energy efficient optimization;self-organized routing protocol;network lifetime

    

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所示。

wl4-t1.gif

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所示。

wl4-t2.gif

    算法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所示。

wl4-t3.gif

    算法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)度策略。

wl4-t4.gif

    傳輸范圍分析是基于不同傳輸范圍內(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)越接近。

wl4-t5.gif

    平均節(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)。

wl4-t6.gif

    圖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ò)大小變化。

wl4-t7.gif

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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。