0 引言

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

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

1 提出的自組織位置感知協議

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

1.1 位置感知結構的構建

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

    算法1：位置感知結構構建算法

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

    輸出：通過錨節點進行完全連接的樹結構。

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

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

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

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

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

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

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

    (8)否則

    (9)運行步驟(2)

    (10)結束

1.2 用于結構維護的拓撲控制

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

    算法2：拓撲控制和結構維護算法

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

    輸出：通過錨節點進行完全連接的樹結構。

    階段一：利用拓撲控制進行拓撲結構簡化（連通性和覆蓋范圍）

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

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

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

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

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

    (6)樹(T)結構維護

    階段二：拓撲結構維護階段。

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

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

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

    (10)在G中利用V_R維護樹結構

1.3 節能機制

    利用位置模型對網絡進行建模，將網絡拓撲作為構建結構的關鍵參數，能量效率如圖3所示，負載均衡算法如算法3所示。

    算法3：負載平衡算法

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

    輸出：一個連接網格結構L表示圖G的子集。

    (1)構建局部網格結構l_n←{V，E}。//在其覆蓋區域內至少含有2個未連接的鄰居節點

    (2)在l_n∈L中構建1個一維的網格集合

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

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

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

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

    (7)向局部網絡添加節點L_n←L∪l∪n

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

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

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

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

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

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

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

1.4 自組織

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

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

    (1)算法在G中的每個WSN上執行；L∈G，L為位置結構

    (2)用i表示整數，w，r∈W_i；//W_i為位置結構節點集合，w為W_i中元素，r為中繼節點

    (3)執行自私行為，調整節點到其最初的位置或維護路由進程

    (4)if將w_i變為w_i+1 or將r_i變為r_i+1，then

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

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

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

    (8) else if ′i′為偶數，將連接調整到i+1個r_i節點

    (9) end

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

    (11)end

2 實驗

    在移動場景和穩定場景下對本文協議進行了仿真實驗和分析。

2.1 實驗設置

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

2.2 結果分析

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

    傳輸范圍分析是基于不同傳輸范圍內所需的中間節點的個數。不同場景下，傳輸范圍在10 m～50 m內變化時，控制節點個數，結果如圖5所示?？梢钥闯?，SEESLP中，當傳輸范圍為10 m時，連通性僅需30個控制節點，隨著傳輸范圍的增加，所需的控制節點個數相應減少，當傳輸范圍為50 m時，相應的控制節點個數為11。由于結構的位置性，MEESLP需要近50%的節點維護連通性。此外，隨著傳輸范圍由40 m增加到50 m，兩種方法的LS尺寸都減少，隨著傳輸范圍的進一步增加，這兩種方法的尺寸會越來越接近。

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

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

2.3 性能比較

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

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

3 結束語

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

參考文獻

[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] 趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優化的WSN定位算法[J].通信學報，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] 康一梅，李志軍，胡江，等.一種低能耗層次型無線傳感器網絡拓撲控制算法[J].自動化學報，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.