能量平衡與QoS保障的無線傳感器網絡機會路由

摘 要： 針對無線傳感器網絡應用中存在大量不可靠通信鏈路，很難實現(xiàn)能效優(yōu)化與QoS保障，提出一種能量平衡與QoS保障的機會路由協(xié)議EQGOR，并結合機會轉發(fā)特征建立了傳輸效率、轉發(fā)時延、轉發(fā)能效與節(jié)點剩余能量模型.提出了一種基于多目標粒子群的自適應轉發(fā)集優(yōu)化算法，該算法兼顧能量與QoS需求，能實現(xiàn)QoS保障并最大化網絡生存時間.仿真實驗表明，相比機會路由GOR與傳統(tǒng)的QoS多路徑路由QuESt，本文提出的EQGOR(Energy balanced and QoS guaranteed Geographic Opportunistic Routing)具有更優(yōu)的QoS與能量效率.

關鍵詞： 無線傳感器網絡；機會路由；能量平衡；服務質量；多目標粒子群優(yōu)化



中圖分類號：TN915 文獻標識碼：A

Energy Balanced and QoS Guaranteed Opportunistic 

Routing for Wireless Sensor Network

YUE Lin1，2， YI Ben-shun1，XIAO Jin-shen1

(1. School of Electronic Information， Wuhan Univ， Wuhan，Hubei 430079，China;

2. China Ship Development and Design Center， Wuhan， Hubei 430064，China)

Abstract:

Because there are a large number of unreliable communication links in wireless sensor network applications， it is difficult to achieve energy efficiency and QoS guarantee.So an energy balanced and QoS guaranteed geographic opportunistic routing protocol (EQGOR) was proposed to solve this problem. Based on opportunistic transmit mechanism， we established the models of forwarding efficiency， forwarding delay， energy efficiency and residual energy， and then proposed an adaptive forwarding set optimization algorithm based on multi-objective particle swarm optimization algorithm， which takes into account both energy and QoS requirement to meet QoS requirement and extend network lifetime. The simulation results have shown that this routing performs better than the opportunistic routing GOR and the traditional multi-path QoS routing QuESt in QoS and energy efficiency.



Key words:wireless sensor networks; opportunistic routing; energy balance; service quality; multi-objective particle swarm optimization



隨著傳感器性能和監(jiān)測精度的不斷提高，在許多無線傳感器網絡(WSN)用于高性能要求的應用中，如目標跟蹤、戰(zhàn)地環(huán)境監(jiān)測等，服務質量(QoS)保障成為設計關鍵目標之一.同時，高效利用傳感器節(jié)點能量和延長網絡壽命仍然是設計的首要目標.而減少通信能耗，選擇能量優(yōu)化的傳輸路徑是延長網絡生存時間的有效方法之一.

為此，學者們提出WSN能量平衡與QoS路由，在路徑建立過程中考慮節(jié)點能量、吞吐量、時延與分組接收率等因素，以滿足QoS性能要求.如Saxena等［1］基于多目標遺傳算法提出一種QoS約束能量高效路由協(xié)議QuESt，協(xié)議根據不同服務特征優(yōu)化時延、帶寬、能耗等指標，建立對應最優(yōu)化路徑.Martirosyan等［2］提出一種能量感知QoS路由，在分簇算法中考慮能量與帶寬、延遲和抖動等，以滿足服務需求.然而，WSN應用中存在大量不可靠通信鏈路，頻繁的數據重傳降低了傳輸效率并增加了能耗，這些確定性QoS路由很難保證較好的服務質量與高能效［3］.

為此，近年來提出了機會路由機制，利用無線廣播的特性，多接收節(jié)點協(xié)作轉發(fā)數據，提升每跳傳輸成功率，可明顯提高傳輸效率與QoS性能.另外，由于WSN節(jié)點眾多、拓撲變化頻繁，多QoS指標的全網路徑生成算法復雜，而基于位置信息輔助的機會路由能明顯減少計算復雜度與路由建立開銷，如Zeng等［4］提出一種地理機會路由GOR，但其側重于提高傳輸效率，沒有關注時延、魯棒性等其他QoS需求.現(xiàn)有的機會路由大多亦針對吞吐量或是時延等某單一目標優(yōu)化，還沒有相關的WSN機會路由考慮到QoS與能量等多目標優(yōu)化問題［5］.

本文提出一種能量平衡與QoS保障的WSN地理機會路由EQGOR (Energy Balanced and QoS guaranteed Geographic Opportunistic Routing)，并提出了一種基于多目標粒子群優(yōu)化算法的自適應轉發(fā)集優(yōu)化算法，實現(xiàn)保障QoS性能與延長網絡生存時間.

1 EQGOR路由協(xié)議描述

設發(fā)送節(jié)點A記錄了所有鄰居節(jié)點s的節(jié)點信息素(a，p，t，e).其中p為分組接收率，t為轉發(fā)時延，e為剩余能量.令d(A，D)為節(jié)點A到目的節(jié)點D的距離，d(s，D)為節(jié)點s到目的節(jié)點D的距離，則節(jié)點s的有效轉發(fā)距離a為：

a=d(A，D)－d(s，D). (1)

其中，剩余能量e與轉發(fā)時延t可以通過節(jié)點間的信息交互而獲得，而對分組接收率p，為了實時反映當前信道接收質量，建議由所接收報文的接收信號強度RSSI(Received Signal Strength Indication)計算出信噪比SNR，再根據Zuniga等［6］提出的WSN節(jié)點分組接收率公式進行計算.

對有效轉發(fā)距離a，若各節(jié)點已知位置信息，則可直接由式(1)計算可得；若未知位置信息，建議匯聚節(jié)點以較大的功率覆蓋全網廣播報文，傳感器節(jié)點根據接收報文的接收信號強度RSSI，結合無線信道傳輸模型估算與匯聚節(jié)點的距離.國內外已有不少基于RSSI距離估算的相關研究，如Anzai等［7］提出了一種針對WSN的基于最大似然函數修正的RSSI估算算法，具有較高的精度與較低的復雜度.凡高娟等［8］也提出了一種基于RSSI的WSN環(huán)境參數分析與修正方案，可明顯提高測距精度.

EQGOR協(xié)議的基本過程為：

1)發(fā)送節(jié)點S向有效傳輸距離大于0(a>0)的節(jié)點發(fā)送請求發(fā)送RTS (Request to Send).

2)收到RTS的空閑節(jié)點反饋準許發(fā)送CTS (Clear to Send).

3)發(fā)送節(jié)點根據收到的CTS確定可用節(jié)點，并根據這些可用節(jié)點的信息素(a，p，t，e)確定最優(yōu)效率下的轉發(fā)集與各節(jié)點轉發(fā)優(yōu)先級.

4)發(fā)送節(jié)點批量發(fā)送數據報文，考慮到節(jié)點存儲空間有限，建議選擇合適的發(fā)送數量.

5)第i優(yōu)先級轉發(fā)節(jié)點接收數據報文后，在確認應答ACK (Acknowledge)中附加數據接收狀態(tài)，并在(i－1)t(i=1，2，3，…；t=10 μs)時間后發(fā)出.

6)第i優(yōu)先級轉發(fā)節(jié)點接收到其他節(jié)點ACK后，刪除隊列中高優(yōu)先級節(jié)點已接收數據報文.

而在步驟3)中，若選擇過多的轉發(fā)節(jié)點會增大協(xié)作開銷，并導致重復傳輸；若選擇低效率或低可靠節(jié)點，則會導致較多能耗或無法滿足QoS需求.因此，接下來對EQGOR協(xié)議傳輸過程進行QoS與能量建模分析，以提供多目標優(yōu)化的理論基礎.

2 QoS與能量建模分析

3.3 狀態(tài)轉移方法

生成初始解后，采用遺傳操作模擬粒子運動，生成新種群.本文建議結合路徑選擇條件，從以下2種操作實現(xiàn)個體狀態(tài)的轉移.

1)交叉操作.當2個染色體有相同優(yōu)先級轉發(fā)節(jié)點時，則可交換該相同優(yōu)先級節(jié)點之后的節(jié)點，以形成新的染色體.如圖2所示，由于存在相同優(yōu)先級w=2的轉發(fā)集節(jié)點s5，則可對兩染色體進行交叉操作，s7與s9交叉后的優(yōu)先級分別為w=4與w=5；由于沒有w=3的節(jié)點，則進行優(yōu)先級規(guī)范后，使s7與s9的優(yōu)先級分別為w=3與w=4.

2)變異操作.變異操作是在轉發(fā)集染色體中選擇一個變異節(jié)點，改變其鄰近節(jié)點優(yōu)先級，從而形成新的轉發(fā)集染色體.如圖3所示，對優(yōu)先級w=2的節(jié)點s5進行變異操作.令s5的鄰近節(jié)點s6的優(yōu)先級w=3，進行規(guī)范化后，即節(jié)點s7與s9優(yōu)先級分別為w=4與w=5.

3.4 評價方法

本文采用TOPSIS評價機制，步驟如下：

1)建立決策矩陣.設優(yōu)化目標為f1，f2，f3，f4 (分別為傳輸效率B、時延倒數1/D、轉發(fā)能效F與剩余能量R)，若有m個候選轉發(fā)節(jié)點為評價對象，令fij為第i個評價對象目標fj(i=1，2，…，m;j=1，2，3，4)的值，則有決策矩陣F=［fij］m×4.

2)構造加權規(guī)范化矩陣.由于各評價目標通常具有不同的數量級，需進行規(guī)范化，得到規(guī)范化矩陣R=［rij］m×4，其中：

rij=fij/∑mi=1f2ij.(15)

采用熵權法計算各指標的權重因子，即根據單項指標的變異程度反映指標權重.

Ej=－1ln m∑mi=1rijln rij. (16)

當rij=0時，規(guī)定rijlnrij=0.根據各指標值的信息熵，計算各指標的權重：

wj=(1－Ej)/∑4k=11－Ek. (17)

由計算的權重因子wj，令zij=wj×rij，即可構造加權規(guī)范化矩陣Z＝［zij］m×4.

3)確定相對接近度.根據指標值得到正理想解和負理想解分別為：

Z+={Z+1，Z+2，Z+3，Z+4}，Z+j=minzij，(18)

Z-={Z-1，Z-2，Z-3，Z-4}，Z-j=maxzij.(19)

評價對象與正理想解和負理想解的距離分別為：

d+i=∑4j=1(zij-Z+j)2，

d-i=∑4j=1(zij-Z-j)2.(20)

評價對象與理想解的相對接近度為：

Di=d-i/(d+i+d-i).(21)

根據Di的大小，可比較評價對象的相對接近度，值越大，相應的評價對象性能越優(yōu).

4 計算復雜度分析

設定初始轉發(fā)節(jié)點數為n，粒子數為np，算法迭代次數為nmax.若對4種不同優(yōu)化目標建立初始解，設效率計算復雜度為O(1)，則有初始解構造算法的計算復雜度為O(4n).

在狀態(tài)轉移過程中，設遺傳算法的進化代數為G，變異概率為P，每次進行變異或是交叉操作之后都要執(zhí)行效率相關計算，其計算復雜度為O(nPG)，故基于多目標粒子群轉發(fā)集優(yōu)化算法的計算復雜度為O(nmaxnp(4n+PGn)).

5 仿真與性能評估

對EQGOR，QuESt［1］與GOR［5］3種路由協(xié)議在不同節(jié)點密度下的傳輸效率、時延、能量效率與生存時間進行比較分析.設定所有協(xié)議每10個數據包后確認應答(ACK).

5.1 仿真實驗參數

實驗采用S-MAC為媒體訪問控制協(xié)議，最大數據傳輸率為250 kb/s，采用NS2的Shadowing射頻傳輸模型以反映無線信道多徑衰落的特征.定義均方差為σdB= 4 dB，耗損系數θ= 2，參考距離d0= 1 m，設定頻率2.4 G下14.126 m的分組接收率為0.9 ，則有通信過渡區(qū)域為［14.126 m，47.987 m］.設定節(jié)點隨機分布在150 m×150 m的正方形區(qū)域中，初始能量值均為50 J，sink節(jié)點位于區(qū)域右上角.控制報文(RTS，CTS，ACK)和數據報文(DATA)大小分別為8字節(jié)和256字節(jié).每采集周期中各數據源都有1 Mb數據需發(fā)送給sink節(jié)點.

5.2 路由性能分析

為驗證路由性能，隨機生成20個數據源，令節(jié)點數量分別為48，60，72，84.

1)傳輸效率.如圖4所示，不同節(jié)點密度下GOR和EQGOR比QuESt的吞吐量有明顯提高.這是因為多節(jié)點協(xié)作轉發(fā)增加了每一跳的傳輸成功率，減少數據包重傳與信道接入時延，提高了傳輸效率.而EQGOR由于兼顧時延、能量等因素，以致傳輸效率略低于GOR.此外，隨著節(jié)點密度增大，待選節(jié)點的增加，使機會路由的傳輸效率明顯提升.

節(jié)點數量

3)能量效率.如圖6所示，通過協(xié)作轉發(fā)，EQGOR與GOR明顯比QuESt每周期采集能耗更少，其中EQGOR通過優(yōu)化每次傳輸的轉發(fā)能效，相比GOR協(xié)議能耗更少.而QuESt協(xié)議采用多路徑傳輸方式，能量消耗最高，在不可靠通信鏈路環(huán)境下的多路徑傳輸方式不僅帶來了時延的增加，而且頻繁的數據重傳帶來了大量的能量消耗.

4)生存時間.如圖7所示，不同節(jié)點密度下EQGOR比GOR與QuESt的網絡生存時間更長.由于兼顧了節(jié)點剩余能量與轉發(fā)能效，EQGOR明顯延長了生存時間.QuESt也具有能量平衡思想，然而多路徑傳輸方式帶來的額外能耗與低傳輸可靠性帶來的大量數據重傳能耗，使得快速消耗節(jié)點能量，反而使網絡生存時間最短.GOR則基于單跳轉發(fā)效率選擇路徑，沒有考慮各節(jié)點能量平衡，一些關鍵位置節(jié)點能量快速耗盡，減少了網絡生存時間.

節(jié)點數量

6 結 論

本文提出的能量平衡與QoS保障的WSN機會路由EQGOR協(xié)議，根據協(xié)議特征建立傳輸效率、轉發(fā)時延、轉發(fā)能效與節(jié)點剩余能量模型，并將兼顧能量與QoS的轉發(fā)節(jié)點集優(yōu)化問題轉換為多目標優(yōu)化問題，采用多目標粒子群算法進行解空間尋優(yōu)，獲得了Pareto最優(yōu)解集，實現(xiàn)QoS性能保障與網絡生存時間優(yōu)化.由于采用熵權法對各目標參數權重因子進行自適應調整，不需要針對不同網絡條件預先調整各優(yōu)化目標權重因子，實現(xiàn)在不同環(huán)境下最大限度地優(yōu)化QoS性能并延長網絡生存時間.

參考文獻

［1］ SAXENA Navrati， ABHISHEK Roy， JITAE Shin. QuESt: a QoS-based energy efficient sensor routing protocol［J］. Wireless Communications and Mobile Computing， 2009， 9(3):417-426.

［2］ MARTIROSYAN Anahit， AZZEDINE Boukerche， RICHARD W， et al. Energy-aware and quality of service-based routing in wireless sensor networks and vehicular ad hoc networks［J］.Annalesdes Telecommunications/Annals of Telecommunications， 2008， 63(11/12):669-681.

［3］ SHAH R C，WIETHOLTER S， WOLISZ A， et al. When does opportunistic routing make sense? ［C］//Third IEEE International Conference on Pervasive Computing and Communications Workshops. Kauai Island:Institute of Electrical and Electronics Engineers Computer Society， 2005: 350-356.

［4］ ZENG Kai， LOU Wen-jing， YANG Jie，et al.On throughput efficiency of geographic opportunistic routing in multihop wireless networks ［J］. Mobile Networks and Applications， 2007， 12(5/6):347-357.

［5］ LIU Hai-tao， ZHANG Bao-xian， HUSSEIN T M， et al. Opportunistic routing for wireless ad hoc and sensor networks: present and future directions［J］.IEEE Communications Magazine， 2009， 47(12):103-109.

［6］ ZUNIGA M， KRISHNAMACHARI B. Analyzing the transitional region in low power wireless links［C］ //Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.Santa Clara， Canada:Institute of Electrical and Electronics Engineers Inc， 2004: 517-526.

［7］ ANZAI D，HARA S.Experimental evaluation of a simple outlier RSSI data rejection algorithm for location estimation in wireless sensor networks［J］.Ieice Transactions on Communications， 2008，91B(11):3442-3449.

［8］ 凡高娟， 王汝傳， 孫力娟. 基于RSSI的無線傳感器網絡環(huán)境參數分析與修正方案［J］.南京郵電大學學報:自然科學版， 2009，29(6):54-57.

FAN Gao-juan，WANG Ru-chuan，SUN Li-juan.Distance-assistant node coverage identification model for wireless sensor networks ［J］. Journal of Nanjing University of Posts and Telecommunications:Natural Science， 2009，29(6):54-57.(In Chinese)

［9］ HEINZELMAN Wendi Rabiner， CHANDRAKASAN Anantha， BALAKRISHNAN Hari. Energy-efficient communication protocol for wireless microsensor networks［C］// Proceedings of the 33rd IEEE Hawaii International Conference on System Sciences(HICSS-33).Maui， Hawaii:IEEE Computer Society， 2000:233-243.

［10］趙紅梅， 李科偉. 基于改進的TOPSIS 法在供應鏈中經銷商的選擇與評價方法研究［J］. 內蒙古農業(yè)大學學報， 2007， 28(2):180-185.

ZHAO Hong-mei，LI Ke-wei.Research of choice and assessment method of distributor in supply chain based on TOPSIS［J］. Journal of Inner Mongolia Agricultural University，2007，28(2):180-185. (In Chinese)