0 引言

    網(wǎng)絡(luò)中傳感器的數(shù)目過多，會使網(wǎng)絡(luò)間通信產(chǎn)生更多的能耗,，集中式算法易導(dǎo)致單個節(jié)點失效^[1-2],。因此，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,，WSN)^[3-4]協(xié)議必須含有分布式定位功能,。文獻[5]利用自組織方式確保連通性并對網(wǎng)絡(luò)進行重新配置，應(yīng)用于網(wǎng)絡(luò)層或節(jié)點層,。然而,，每個節(jié)點都包含在自組織網(wǎng)絡(luò)中時,，無法保證其能量效率^[6],。

    本文提出一種WSN能效優(yōu)化的自組織位置感知協(xié)議(Energy Efficient Self-organized Location aware Protocol，EESLP),，根據(jù)拓撲控制進行自組織處理,，綜合考慮兩個WSN參數(shù)：數(shù)據(jù)包投遞率和能耗，在增加數(shù)據(jù)包傳輸率的同時降低了能耗,。

1 提出的自組織位置感知協(xié)議

    本文協(xié)議分四個步驟進行路由選擇,，工作流程如圖1所示。

1.1 位置感知結(jié)構(gòu)的構(gòu)建

    圖2所示為基于位置感知構(gòu)建的樹結(jié)構(gòu),，其中,，黑色節(jié)點表示Sink節(jié)點（根節(jié)點），灰色節(jié)點表示錨主干節(jié)點,，白色節(jié)點表示葉節(jié)點,。位置感知結(jié)構(gòu)構(gòu)建算法如算法1所示。

    算法1：位置感知結(jié)構(gòu)構(gòu)建算法

    輸入：含有V個頂點(V←v₁,，v₂,，…,，v_n)和E條邊的非連通圖G。

    輸出：通過錨節(jié)點進行完全連接的樹結(jié)構(gòu),。

    (1)在圖G選取根頂點V_R,，即V_R∈G。//V_R是Sink節(jié)點

    (2)添加連接V_R和v_i以及節(jié)點v_i和v_j的邊e_i,。//i,，j=1，2,，3…

    (3)若v_i和v_j是V_R的兩跳距離節(jié)點,，則執(zhí)行步驟(4)

    (4)檢測C(連通性)。//利用G圖中的兩個未連接鄰居節(jié)點將v_i和v_j連接

    (5)選取v_abi和v_abj作為第一層主干錨節(jié)點,，命名為V_ab1和V_ab2,。//V_ab表示主干錨節(jié)點

    (6)持續(xù)步驟(3)～(5)，直到圖G中的所有節(jié)點都連接

    (7)通過V_abi和V_abj將位置信息告知V_R

    (8)否則

    (9)運行步驟(2)

    (10)結(jié)束

1.2 用于結(jié)構(gòu)維護的拓撲控制

    利用拓撲控制維護結(jié)構(gòu)貫穿整個過程,，通常通過減少或簡化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)來進行節(jié)能,，同時維持網(wǎng)絡(luò)的一些重要特性（如連通性和覆蓋范圍等）^[7]。拓撲控制和維護算法如算法2描述,。

    算法2：拓撲控制和結(jié)構(gòu)維護算法

    輸入：含有V個頂點(V←v₁,，v₂，…,，v_n)和E條邊的未連接圖G,。

    輸出：通過錨節(jié)點進行完全連接的樹結(jié)構(gòu)。

    階段一：利用拓撲控制進行拓撲結(jié)構(gòu)簡化（連通性和覆蓋范圍）

    (1)當V中節(jié)點v（葉節(jié)點）的能量減少或改變位置時,。//節(jié)點能量耗盡或節(jié)點處于運動過程中

    (2)v_ai←v_i,。狀態(tài)的改變指向錨主干

    (3)v_i←v_abi←V_R。//連通維護層級V_R,，v_bi和v,，其中v與新錨點v_bi連接

    (4)若v_bi的一跳鄰居節(jié)點中含有一跳未連接的路徑，將v_bi添加到v_b上

    (5)更新G中所有的由v_i到v_abi的連接

    (6)樹(T)結(jié)構(gòu)維護

    階段二：拓撲結(jié)構(gòu)維護階段,。

    (7)使G含有v_i,，v_ab和V_R

    (8)若P(v_i≠v_ab≠V_R)能量不等

    (9)則從G移出v_i，當需要時恢復(fù)v_i

    (10)在G中利用V_R維護樹結(jié)構(gòu)

1.3 節(jié)能機制

    利用位置模型對網(wǎng)絡(luò)進行建模,，將網(wǎng)絡(luò)拓撲作為構(gòu)建結(jié)構(gòu)的關(guān)鍵參數(shù),，能量效率如圖3所示，負載均衡算法如算法3所示,。

    算法3：負載平衡算法

    輸入：無向圖G=(V,，E)。//V,，E分別表示頂點和邊的集合,。

    輸出：一個連接網(wǎng)格結(jié)構(gòu)L表示圖G的子集,。

    (1)構(gòu)建局部網(wǎng)格結(jié)構(gòu)l_n←{V，E},。//在其覆蓋區(qū)域內(nèi)至少含有2個未連接的鄰居節(jié)點

    (2)在l_n∈L中構(gòu)建1個一維的網(wǎng)格集合

    (3)L(v)∈{G},，這里L≥2，3,，4,，…。//v表示一個頂點

    (4)在集合L中尋找一個子集合A用于更替路由,，如l₁,，l₂，…,，l_n∈V

    (5)若l₁,，l₂為更替路由虛擬節(jié)點。//節(jié)點度l₁,，l₂≥1或2

    (6)則將葉節(jié)點n與L或l連接

    (7)向局部網(wǎng)絡(luò)添加節(jié)點L_n←L∪l∪n

    (8)當L(v)改變其位置時,。//v，u是L(局部結(jié)構(gòu))中的頂點

    (9)l(u)←L(v),。//通過′l′維護連接′L′,，l是L的子集

    (10)只有當l一跳連接u和v，則增加v,，u

    (11)類似的,，添加一跳l₁，l₂,，…,，l_n到L的其他節(jié)點

    (12)(l，n)←更新i,。//i為信息狀態(tài)

    (13)若l₁在一跳中不可利用或不在傳輸范圍內(nèi),。//僅用于較小傳輸范圍

    (14)n←l,。//葉節(jié)點(n)變成虛擬節(jié)點

1.4 自組織

    利用自組織方式^[8]降低節(jié)點或網(wǎng)絡(luò)中的消息復(fù)雜度,，為避免碰撞、競爭和連接失敗等問題,，通過重建和位置結(jié)構(gòu)的拓撲過程獲得自組織,，利用分布式定位算法實現(xiàn)位置結(jié)構(gòu)的拓撲過程。若一個節(jié)點希望進入任何一個工作區(qū)域,，則會對它的服務(wù)進行分層限制,，并產(chǎn)生支持每個節(jié)點的平面路由。在真實的數(shù)據(jù)傳輸過程中（如網(wǎng)絡(luò)電話）,，僅有平面路由是不行的,。與此同時,，在一個分層系統(tǒng)中，將實時傳輸設(shè)置為高優(yōu)先級,，并將節(jié)點連接到低擁堵的區(qū)域,。為了減少路由和控制開銷，允許中間節(jié)點或中繼節(jié)點處理其他節(jié)點的擁堵情況,。自組織算法如算法4所示,。

    算法4：EESLP中的自組織算法

    (1)算法在G中的每個WSN上執(zhí)行；L∈G,，L為位置結(jié)構(gòu)

    (2)用i表示整數(shù),，w，r∈W_i,；//W_i為位置結(jié)構(gòu)節(jié)點集合,，w為W_i中元素，r為中繼節(jié)點

    (3)執(zhí)行自私行為,，調(diào)整節(jié)點到其最初的位置或維護路由進程

    (4)if將w_i變?yōu)閣_i+1 or將r_i變?yōu)閞_i+1,，then

    (5)在G中尋找所有可能執(zhí)行自私行為的自組織節(jié)點

    (6)if w=w(i)，then

    (7) if ′i′是奇數(shù),，then w支撐奇數(shù)連接（最小度）

    (8) else if ′i′為偶數(shù),，將連接調(diào)整到i+1個r_i節(jié)點

    (9) end

    (10)else 為連通性選取新的wi

    (11)end

2 實驗

    在移動場景和穩(wěn)定場景下對本文協(xié)議進行了仿真實驗和分析。

2.1 實驗設(shè)置

    仿真中,，接收功率設(shè)置為0.1 W,，傳輸功率設(shè)置為0.281 4 W。利用NS2仿真器構(gòu)建含有200個節(jié)點,、大小為1 000 m×1 000 m的WSN區(qū)域,，聞訊間隔為0.90 s，采用隨機位點模型,。所有節(jié)點的初始能量為0.25 J,，節(jié)點的傳輸范圍為10 m～50 m，仿真持續(xù)時間為120 s,。在第一種場景中,，所有節(jié)點都是固定的，并且按序生成10個UDP會話,，每個會話傳輸50個恒定比特率（CBR）數(shù)據(jù)包,。在初始階段，所有節(jié)點都是黑色的,，擁有紅色節(jié)點的度為5,；用黃色表示運動節(jié)點。在移動體系結(jié)構(gòu)中,，設(shè)置節(jié)點的移動速率為1 m/s,。利用穩(wěn)定能效自組織位置感知協(xié)議(Stable Energy Efficient Self-organized Location aware Protocol,，SEESLP)表示穩(wěn)定性分析，移動能效自組織位置感知協(xié)議(Mobile Energy Efficient Self-organized Location aware Protocol,，MEESLP)表示移動場景分析,，另外，每個場景下設(shè)置2種覆蓋區(qū)域范圍,，I和II分別表示25 m和50 m的覆蓋區(qū)域,。

2.2 結(jié)果分析

    由于網(wǎng)絡(luò)是利用標記策略形成，因此作為關(guān)鍵因素的位置路由成為性能比較的重點,。在相同的參數(shù)設(shè)置下,，隨機生成10個連接的UDGs，計算每個圖的LS以及平均LS尺寸,，LS表示位置結(jié)構(gòu)中用于維護連通性所需的節(jié)點個數(shù),，結(jié)果如圖4所示。由圖4可知,，SEESLP-II策略僅需要8%的節(jié)點去維護連通性,。根據(jù)鄰近Sink節(jié)點識別機制，位置結(jié)構(gòu)中僅需12個節(jié)點連接Sink節(jié)點與源節(jié)點,。另一方面,，MEESLP-I需要25%的節(jié)點進行移動維護，這是因為在移動場景下,，具有高的節(jié)點密度和節(jié)點移動性,，節(jié)點之間需要交換更多的控制負載。同時還可以看出,，若網(wǎng)絡(luò)是稀疏的,，網(wǎng)絡(luò)中的大多數(shù)節(jié)點將會被一個位置結(jié)構(gòu)包含，這與高或低的節(jié)點度策略無關(guān),。若網(wǎng)絡(luò)變得稠密,，利用高節(jié)點度減小EESLP的尺寸。因此,，最高節(jié)點度策略優(yōu)于最小節(jié)點度策略,。

    傳輸范圍分析是基于不同傳輸范圍內(nèi)所需的中間節(jié)點的個數(shù)。不同場景下,，傳輸范圍在10 m～50 m內(nèi)變化時,，控制節(jié)點個數(shù)，結(jié)果如圖5所示,。可以看出,，SEESLP中,，當傳輸范圍為10 m時,，連通性僅需30個控制節(jié)點，隨著傳輸范圍的增加,，所需的控制節(jié)點個數(shù)相應(yīng)減少,，當傳輸范圍為50 m時，相應(yīng)的控制節(jié)點個數(shù)為11,。由于結(jié)構(gòu)的位置性,，MEESLP需要近50%的節(jié)點維護連通性。此外,，隨著傳輸范圍由40 m增加到50 m,，兩種方法的LS尺寸都減少，隨著傳輸范圍的進一步增加,，這兩種方法的尺寸會越來越接近,。

    平均節(jié)點度分析中，評估了節(jié)能方法的可擴展性,，如圖6所示,，網(wǎng)絡(luò)的密度限制為200個節(jié)點。從圖中可知,，SEESLP-II僅需4個中繼節(jié)點,。由于當一個支配者的節(jié)點級別增加，它就不能連接所有的節(jié)點,，因此與傳輸范圍分析相比,，節(jié)點級別分析需要更大量的中間節(jié)點。

    圖7顯示了數(shù)據(jù)包投遞率的比較,。一個數(shù)據(jù)包的大小在16 bit到128 bit之間變化,，利用本文協(xié)議傳輸數(shù)據(jù)包并對包投遞率進行分析。在WSN網(wǎng)絡(luò)中存在3種會影響PDR的情況：（1）節(jié)點發(fā)送功率變化,；（2）節(jié)點數(shù)量變化,；（3）網(wǎng)絡(luò)大小變化。

2.3 性能比較

    將本文協(xié)議與文獻[5],、文獻[7]和文獻[8]提出的協(xié)議進行比較,，結(jié)果如圖7(a)所示。從圖中可以看出,，本文協(xié)議具有最優(yōu)的數(shù)據(jù)包投遞率,。

    本文協(xié)議的一個重要衡量指標是能量分析。在初始階段,，所有節(jié)點的能量設(shè)置為0.25 J,，將0.1 J設(shè)置為能量閾值。將本文協(xié)議與文獻[5]、文獻[7]和文獻[8]提出的協(xié)議進行比較,，結(jié)果如圖7(b)所示,。從圖7(b)可以看出，本文協(xié)議在120 s后網(wǎng)絡(luò)節(jié)點平均能量仍然能夠保持70%,，很好地均衡了網(wǎng)絡(luò)節(jié)點能量,，提高了網(wǎng)絡(luò)壽命。

3 結(jié)束語

    本文提出了一種利用能效優(yōu)化的自組織位置感知協(xié)議,，根據(jù)主干錨節(jié)點的位置感知將網(wǎng)絡(luò)構(gòu)建成樹結(jié)構(gòu),，利用拓撲控制優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)來維持網(wǎng)絡(luò)的連通性和覆蓋范圍。同時在路徑選擇過程中加入節(jié)能機制,，從而均衡網(wǎng)絡(luò)負載,。在運行過程中，利用自組織方式最小化消息傳輸和接收次數(shù),，降低消息復(fù)雜度,，減少協(xié)議開銷。未來研究將會考慮傳感器網(wǎng)絡(luò)快速運動情況,。

參考文獻

[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] 趙雁航，錢志鴻,，尚小航,，等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報，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ǎng)絡(luò)拓撲控制算法[J].自動化學(xué)報,，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.