基于最優(yōu)連通功率控制的WSNs跨層路由優(yōu)化算法*

孫 毅， 孫 躍， 曾璐琨， 陸 俊

(華北電力大學 電氣與電子工程學院，北京 102206)

0 引 言

網絡生命周期延長優(yōu)化是無線傳感器網絡(wireless sensor networks，WSNs)[1]路由算法設計的首要研究問題。但由于傳感器節(jié)點能量受限，且隨機部署，拓撲結構變化頻繁，傳統的路由協議難以保障網絡鏈路的穩(wěn)定性和數據的實時性等要求。而功率控制技術不僅能夠有效控制并降低無線通信過程中的能耗，同時對路由協議中轉發(fā)節(jié)點的選擇和數據融合中融合節(jié)點的選擇起著重要的作用[2]，是延長WSNs生命周期、實現服務質量(quality of service,QoS)支持的有效手段。

跨層路由優(yōu)化是通過節(jié)點自適應功率控制機制，在保證網絡連通性和減少通信干擾條件下，提高數據實時、可靠的傳輸，同時優(yōu)化網絡能量利用率[3]。目前，研究者們針對能量高效的跨層路由協議已經取得一些研究成果。文獻[4]采用一種自適應優(yōu)化轉發(fā)候選集和發(fā)射功率機制，延長網絡生存周期;文獻[5]通過消除冗余節(jié)點和休眠調度機制設計了一種節(jié)能型路由算法;文獻[6]基于最優(yōu)鄰居節(jié)點數的建立功率調度表，并對干擾節(jié)點發(fā)送反饋幀控制其睡眠/偵聽，從而降低通信能耗;文獻[7]在AODV路由協議的基礎上，為節(jié)點分配不同的功率等級，包括：廣播功率、單播功率和最大發(fā)射功率，以有效降低數據傳輸的能耗。

文獻[4～7]雖然大部分算法在選取下一跳節(jié)點時綜合了剩余能量因素，以延長網絡生命周期，但是，以上算法沒有全面地考慮網絡連通情況和可能產生的空洞現象，易導致數據傳輸的實時性和可靠性下降。

針對上述問題，本文提出了一種基于最優(yōu)連通功率控制的跨層路由優(yōu)化(cross-layer routing optimization based on optimal connectivity power control，CRCP)算法。算法通過最優(yōu)鄰居節(jié)點數確定節(jié)點最優(yōu)連通功率，以此來實現網絡最優(yōu)連通，降低熱點地區(qū)干擾程度；綜合節(jié)點干擾等級、剩余能量和位置信息動態(tài)選取下一跳節(jié)點，延長網絡生命周期，保障路由QoS。

1 CRCP算法

1.1 問題描述

CRCP算法重點解決兩個方面問題：一方面是MAC層針對不同類型數據包進行功率等級的調整，并將節(jié)點MAC層的功率調度信息提供給物理層；另一方面,網絡層通過共享物理層的節(jié)點狀態(tài)信息來動態(tài)選取最優(yōu)轉發(fā)節(jié)點，建立QoS保證的傳輸路徑。GPSR算法[8]基于局部最優(yōu)的貪婪算法，無需維護網絡拓撲，路由開銷小，但是容易造成局部節(jié)點死亡，導致網絡割裂。每個節(jié)點以固定的功率等級傳輸數據，不僅造成了過多的能量開銷，還易形成熱點區(qū)域。固定功率(通信半徑R=100 m)網絡連通性與節(jié)點干擾強度如圖1所示。

圖1 網絡連通性與節(jié)點干擾強度圖(R=100 m)

為了降低節(jié)點競爭強度和通信能耗，通常需要節(jié)點采用較小的發(fā)射功率，這使得網絡連通性變差，從而導致許多節(jié)點無法建立穩(wěn)定的通信鏈路，形成孤島節(jié)點群現象，固定功率(通信半徑R=60 m)網絡連通性與節(jié)點干擾強度如圖2所示。

圖2 網絡連通性與節(jié)點干擾強度(R=60 m)

因此，如何降低高密度區(qū)域節(jié)點的沖突區(qū)域，保證節(jié)點競爭信道的公平性和選擇低干擾、高能效的路由進行數據傳輸，是WSNs功率控制路由協議研究的重點問題。CRCP算法分為最優(yōu)功率控制和路徑建立階段。

1.2 最優(yōu)連通功率控制

本節(jié)的討論是基于以下假設：

1)物理層中傳輸的幀采用的離散功率等級可以由MAC層通知。

2)在物理層可以測量接收幀的接收信號強度指示器(RSSI)。

3)節(jié)點的位置可以通過GPS獲取。

節(jié)點發(fā)射功率的級別與節(jié)點的鄰居節(jié)點數量密切相關。大量研究表明，在最優(yōu)鄰居節(jié)點數[9]為6～8個時，能夠顯著地提高信道利用率和網絡吞吐量。節(jié)點最優(yōu)連通功率定義為：對于網絡中的任意節(jié)點v，計算它的最優(yōu)鄰居節(jié)點的個數為Nopt，則節(jié)點v到它的任意鄰居節(jié)點u的最優(yōu)發(fā)射功率定義為

Popt(u),1≤u≤Nopt.

(1)

最優(yōu)連通功率定義為

Poc(v)=max{Popt(u)|(1≤u≤Nopt)}.

(2)

雙向連通的定義為

(3)

其中，n和m為路由跳數，存在n>0,m>0;Pn(i,j)>0為經過n跳，節(jié)點i能夠與節(jié)點j通信的概率;Pm(j,i)>0為經過m跳，節(jié)點j能夠與節(jié)點i通信的概率。

為了在保證網絡QoS的基礎上，最大限度延長網絡壽命，采取的措施是：初始化階段采用最大功率廣播消息，進行最優(yōu)鄰居發(fā)現；之后,當節(jié)點發(fā)送控制分組時，采用最優(yōu)連通功率Poc(i)來提高網絡的性能；當節(jié)點發(fā)送數據分組時，采用最優(yōu)發(fā)射功率Popt(i)將數據分組發(fā)送至最優(yōu)鄰居節(jié)點，因為數據分組的數據量大且持續(xù)時間長，這樣可以最大限度降低能耗。

1.3 路徑建立

路徑建立由源節(jié)點請求發(fā)起，綜合轉發(fā)節(jié)點的干擾等級、剩余能量、位置信息3個屬性，選取路由代價最小的鄰居節(jié)點。發(fā)送節(jié)點根據MAC層收到鄰居節(jié)點回復的應答消息，計算源節(jié)點前向區(qū)域中候選節(jié)點的SINR為

(4)

干擾等級定義為

(5)

為獲得較低的干擾，可以通過功率等級的調整，限制潛在干擾節(jié)點的數量和節(jié)點同時進行數據發(fā)送的概率來控制節(jié)點受干擾程度。本文通過自適應的最優(yōu)連通功率控制方法來降低鄰居節(jié)點對其干擾，減少丟包率。

計算隸屬于低干擾群組中鄰居節(jié)點i路由代價函數為

(6)

其中，Eres為節(jié)點的剩余能量，Eini為節(jié)點的初始能量，d(S,D)為源節(jié)點到Sink節(jié)點的距離，d(i,D)為前向區(qū)域中下一跳節(jié)點i與Sink節(jié)點之間的距離，lgSINRi為前向區(qū)域中低干擾群組節(jié)點i的信號噪聲干擾比。

路徑建立過程的具體實現步驟如下：

1)網絡初始化：每個節(jié)點以最大功率廣播“Hello”控制幀，進行鄰居發(fā)現過程。該幀中包括自身ID、剩余能量、自身位置信息參數。收到該數據幀的鄰居節(jié)點回復應答消息，計算兩點之間的通信距離和SINR。

2)節(jié)點功率控制：每個節(jié)點在最大鄰居節(jié)點集合中，按照式(2),式(3)選取最優(yōu)鄰居節(jié)點，以建立雙向連通鏈路。

3)干擾等級劃分：當前節(jié)點MAC層根據收到的應答消息中的SINR和目標SINR閾值進行比較，為轉發(fā)節(jié)點集劃分干擾等級，并將該信息通知網絡層。

4)計算路由代價：當前節(jié)點根據鄰居節(jié)點信息，按照式(6)計算低干擾等級中備選節(jié)點的路由代價，選取綜合代價最小的鄰居節(jié)點作為下一跳。

2 仿真結果與分析

為了驗證CRCP算法的性能，本文對CRCP和GPSR算法設定了3組實驗進行對比分析。節(jié)點隨機分布在場景區(qū)域為500 m×500 m的范圍內，節(jié)點數為150個，數據包為2 048 bits，初始能量為1 J，Eelec為50 nJ/bit，εamp為0.001 3 pJ/bit/m4，εfs為100 pJ/bit/m2。Sink節(jié)點位置在(0,0)m處，源節(jié)點為距離Sink節(jié)點的最遠節(jié)點。

2.1 最優(yōu)連通功率控制性能分析

圖3給出了采用最優(yōu)連通功率建立的雙向連通鏈路。CRCP算法實現了節(jié)點間雙向連通路由，同時有效降低網絡中熱點區(qū)域干擾強度，避免孤立節(jié)點群的產生。隨著網絡運行導致節(jié)點部分失效，CRCP算法能夠實時感知最優(yōu)鄰居節(jié)點，自適應調整發(fā)送功率，保證網絡的雙向連通。

圖3 最優(yōu)連通功率雙向連通鏈路

節(jié)點干擾強度可以被定義為傳輸范圍內的期望競爭同一信道的鄰居節(jié)點數。當節(jié)點鄰居節(jié)點數越高，存在較多的節(jié)點競爭同一無線信道，即較高的干擾強度。從表1中可以看出：CRCP算法通過感知最優(yōu)鄰居節(jié)點，動態(tài)調整節(jié)點功率，有效降低了節(jié)點潛在的干擾和競爭強度。

表1 節(jié)點干擾強度

2.2 QoS分析

圖4比較了在不同網絡規(guī)模的情況下，CRCP和GPSR算法的路由跳數。仿真結果表明:在網絡中節(jié)點數分別為150,160,170,180,190,200時，CRCP與GPSR算法相比，時延分別降低了21.1 %，20 %，16.7 %，15 %，5 %，10 %。當網絡節(jié)點數目較少時，CRCP算法能夠保證網絡的連通性，保證數據傳輸的實時性要求。

圖4 路由跳數

圖5反映了CRCP和GPSR算法丟包率對比曲線。當節(jié)點數從150～200時，CRCP算法的丟包率較GPSR分別降低了2 %，11.8 %，11.4 %，18.9 %，25.3 %，27.5 %。CRCP算法隨著網絡規(guī)模的增大，丟包率保持平穩(wěn)變化。這主要由于CRCP算法通過最優(yōu)鄰居節(jié)點策略，降低了每個節(jié)點潛在的干擾節(jié)點數量。因此，CRCP算法具有較高的傳輸可靠性。

圖5 丟包率

2.3 網絡生命周期

圖6比較了CRCP算法和GPSR算法網絡生命周期,可以看出:CRCP算法的網絡生命周期與GPSR算法相比，提高了12.5 %。這是因為采用最優(yōu)連通功率控制在保證網絡的連通性的同時，能夠顯著降低節(jié)點發(fā)射功率的富余量，以延長網絡的生命周期。

圖6 網絡生命周期

3 結 論

本文在分析了GPSR算法的基礎上，提出了一種CRCP算法。與GPSR算法相比，在選擇下一跳轉發(fā)節(jié)點時，綜合考慮了節(jié)點剩余能量、位置信息和干擾等級，從而均衡網絡的能量消耗，降低數據分組碰撞概率，保證數據傳輸的實時性要求。仿真結果表明：CRCP算法在拓撲頻繁變化的網絡中，保證網絡的穩(wěn)定連通，最大限度延長網絡生命周期，優(yōu)化傳輸時延和可靠性等QoS要求。

參考文獻:

[1] 孫利民,李建中,陳 渝,等. 無線傳感器網絡[M].北京:清華大學出版社,2005.

[2] 李方敏,徐文君,劉新華.無線傳感器網絡功率控制技術[J].軟件學報,2008,19(3):716-732.

[3] 唐 勇,周明天,張 欣.無線傳感器網絡路由協議研究進展[J].軟件學報,2006,17(3):410-421.

[4] 張大鵬,康會莉,王新生.WSNs中一種基于EIETX 的自適應功率控制的機會路由[J].傳感器與微系統,2013,32(3):43-48.

[5] 李 莎,劉三陽,馮海林.基于網格的無線傳感器網絡節(jié)能路由算法[J].計機工程,2011,37(9):144-146.

[6] 于 凱,謝志軍,金 光,等.基于功率控制的無線傳感器網絡MAC協議研究[J].傳感技術學報，2013,26(9):1297-1302.

[7] 王 杉,魏急波,鄧書林,等.一種新的跨層功率控制無線傳感器網絡路由協議[J].傳感技術學報，2008,21(8):1402-1405.

[8] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proc of the 6th Annual International Conference on Mobile Computing and Networking,New York:ACM,2000:243-254.

[9] 李方敏,劉新華,曠海蘭,等.基于最優(yōu)連通功率的無線傳感器網絡穩(wěn)定成簇算法[J].通信學報,2009,30(3):75-83.