無線多媒體傳感器網絡能量均衡的QoS路由算法*

楊 冰 ，鄧曙光 ，文雙春

(1.湖南大學 信息科學與工程學院,湖南 長沙 410082;2.湖南城市學院 通信與電子工程學院，湖南 益陽 413000)

無線多媒體傳感器網絡能量均衡的QoS路由算法*

楊 冰1,2，鄧曙光2，文雙春1

(1.湖南大學 信息科學與工程學院,湖南 長沙 410082;2.湖南城市學院 通信與電子工程學院，湖南 益陽 413000)

為保障能量受限的無線多媒體傳感器網絡(WMSNs)多服務質量(QoS)需求，提出了一種能量均衡的QoS路由 (EBQR) 算法。該算法通過蟻群優化將網絡帶寬、時延、丟包率和能量等因素作為目標函數，并根據函數值大小動態調整蟻群信息素的揮發系數和濃度增量，提供網絡業務中滿足不同QoS需求的最優路徑。仿真結果表明：與AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端時延降低了16 %，丟包率減少22 %，生命周期延長了近50 %，有效實現了網絡中節點能耗的均衡性。

無線多媒體傳感器網絡； 能量均衡； 服務質量路由； 蟻群算法

0 引 言

隨著傳感器技術和無線通信技術的不斷發展，無線傳感器網絡(wireless sensor networks，WSNs)以其自組織、低成本等特點被廣泛應用于社會各種活動中[1，2]。監測環境日趨復雜多變，對監測數據的要求越來越高,為了實現細粒度、精準信息的監測，人們將具有音頻、視頻、圖像等多媒體信息感知功能的新型傳感器節點引入到傳感器網絡中[3，4]，由此催生了無線多媒體傳感器網絡(wireless multimedia sensor networks,WMSNs)。網絡服務質量(quality of service,QoS)是網絡提供給應用或用戶服務性能的一種測量[5]。傳統的QoS路由算法不能直接適用于WMSNs，因為它具有能量等資源有限和對QoS的要求比較高等特點。WMSNs的QoS要求，包括可用性、吞吐量、時延、時延抖動、丟包率、能耗等參數[6，7]。

針對WMSNs的特點，國內外對QoS路由問題開展了大量研究[8～10],這些研究主要集中在實時性、可靠性或能量約束等方面。例如:文獻[8]提出了一種基于能量感知的可靠路由機制，充分考慮節點的剩余能量和路徑的可靠性，選擇相應的路徑，從而提高可靠性和降低能耗；文獻[9]提出了一種保證實時性的路由協議，通過考慮轉播速率和剩余能量來降低平均時延和延長網絡生命周期；文獻[10]提出了角度區分服務的路由機制，根據實時和非實時數據進行相應處理，滿足其需求并有效均衡能量消耗。此外，也有一些針對多QoS約束條件路由問題的研究,例如:通過綜合考慮路徑的帶寬、時延、丟包率和能耗等方面之間的均衡問題，在滿足這些需求的同時盡量減少網絡能耗延長網絡生命周期[11～13]。從如上所述的研究來看，在能量消耗方面，存在某些關鍵節點被頻繁使用而過早死亡或為避開能量過低節點而導致總能耗增大等問題。文獻[14]利用能量因數有效解決了最小化路由通信所消耗總能量和最大化網絡生命周期的問題。本文基于能量因數這一思想，提出一種能量均衡的QoS路由(EBQR)算法，該算法既滿足網絡對帶寬、時延、丟包率、時延抖動、能耗的QoS需求，同時又能均衡網絡中節點的能耗，并有效降低數據傳輸的總能耗。

1 WMSNs中EBQR模型

WMSNs可抽象為一個賦權圖G=(V,E)，其中，V為網絡的中節點集合，V={v1,v2,…,vn}，E為網絡中節點間通信的鏈路集，E={e1,e2,…,em}。對于任意鏈路e∈E，有e=(vi,vj)，vi∈V,vj∈V,i≠j。每條鏈路具有(bandwidth(eij)，delay(eij)，jitter(eij)，loss(eij))4個屬性的QoS特征值，分別表示節點vi到節點vj的帶寬、時延、時延抖動、丟包率。每個節點具有能量energy(vi)的特征。

QoS路由選擇是在圖G=(V,E)中尋找到一條從源節點到目的節點滿足QoS約束條件的路徑P=(vs,…,vd),約束關系如下：

1)條件1:帶寬約束

BP=min{bandwidth(eij)}≥Bmin,?vi,vj∈P,

(1)

式中Bmin為路徑上要求的最小帶寬。

2)條件2:時延約束

DP=∑delay(eij)≤Dmax, ?vi,vj∈P,

(2)

式中Dmax為路徑上要求的最大時延和。

3)條件3:時延抖動約束

JP=∑jitter(eij)≤Jmax,?vi,vj∈P,

(3)

式中Jmax為路徑上要求的最大時延抖動和。

4)條件4:時延抖動約束

LP=1-∏(1-loss(eij))≤Lmax,?vi,vj∈P,

(4)

式中Lmax為路徑上允許的最大丟包率。

5)條件5:能量約束

EnP=energy(vi)≥Enmin,?vi∈P,

(5)

式中Enmin為路徑上每個節點要求的最小能量。

6)條件6:目標函數

(6)

式中α,β,γ,δ,φ分別為帶寬、時延、時延抖動、丟包率和能量的比重系數，α+β+γ+δ+φ=1，EF為能量因數

(7)

式中IE為節點的初始能量，M為量化級。

本文的目標是在滿足條件1～條件5的情況下使得F值最小。

2 EBQR算法描述

蟻群算法[15～17]是一種模擬螞蟻群體覓食行為的仿生優化算法，采用正反饋并行催化機制，具有較強的魯棒性、優良的分布式計算機功能以及易于與其他啟發算法結合等優點，在諸多領域已得到廣泛應用。WMSNs中信息的動態性、隨機性、異步性等特點與蟻群算法中的螞蟻移動非常相似，因此，利用蟻群算法來解決WMSNs中的復雜問題具有重要意義。本文根據目標函數值的大小動態調整信息素揮發系數和信息素濃度增量，尋找滿足QoS約束條件的最佳路由。

WMSNs中的每個節點都執行同樣的路由選擇算法，從源節點向目的節點周期性地發送螞蟻，并根據QoS需求找到滿足條件的路徑。

步驟1：初始化參數，產生前向螞蟻。

步驟2：當前向螞蟻到達節點i時，先判斷該節點是中間節點還是目的節點，同時判斷是否滿足QoS約束指標中的條件。若為中間節點且滿足QoS約束指標，則按式(8)選擇轉移概率大的鄰居節點j作為螞蟻移動的下一個節點，重復步驟(2)

(8)

(9)

若為中間節點且不滿足QoS約束指標，則執行步驟(3)，若為目的節點，則執行步驟(4)。

步驟3：停止轉發前向螞蟻，在節點i處產生一個后向螞蟻，按式(10)更新前向螞蟻所走過路徑上的信息素

τij(t+1)=(1-ρ1)τij(t).

(10)

重復執行步驟(3)，直到到達源節點，執行步驟(5)。

步驟4：當前向螞蟻到達目的節點時，判斷是否滿足QoS約束指標，并按式(6)計算目標函數F，丟棄前向螞蟻并產生后向螞蟻，根據目標函數值F的大小按式(11)或式(13)更新前向螞蟻所走路徑上的信息素濃度，直到到達源節點

τij(t+1)=(1-ρ0)τij(t)+Δτij(t),

(11)

Δτij(t)=Q1/F.

(12)

當目標函數F的最小值在連續n次的迭代過程中均無變化時

τij(t+1)=(1-ρ2)τij(t)+Δτij(t),

(13)

Δτij(t)+Q2/F.

(14)

步驟5：當源節點收到返回的后向螞蟻，信息素被更新，同時丟棄該螞蟻。轉到步驟(2)反復執行直到到達設定的迭代次數，算法終止，輸出目標函數值最小的路徑。

3 仿真與分析

為驗證本文所提算法的有效性，建立仿真環境進行驗證分析。假設在200 m×200 m的區域里隨機部署100個無線傳感器節點(包括Sink節點)，Sink的位置固定于(0,0)m，該節點的能量不受限制(在處理過程中忽略該點的能量消耗問題)。設定其他節點的初始能量為15 J，發送數據和接收數據能耗為50 nJ/bit，通信半徑為70 m，網絡帶寬為[1,10]Mbps之間的隨機數，鏈路之間的時延為[10,20] ms之間的隨機數，鏈路之間的丟包率為[0,0.045]之間的隨機數。同時假設QoS需求為Bmin=2 Mbps，Dmax=100 ms，Lmax=0.15，Enmin=0.2 J，取α=0.1，β=0.4，γ=0，δ=0.4，φ=0.1。

在上述環境下，對本文提出的EBQR算法和文獻[12,13]的算法進行仿真，分別從平均傳輸時延、平均丟包率、平均能量消耗以及網絡生命周期4個方面進行性能比較。其中，平均傳輸時延為不同測試時間段源節點傳送有效數據包到匯聚節點所用的平均時間。丟包率為源節點傳送有效數據包到匯聚節點丟失數據包的數量所占發送數據包的比率。平均能量消耗為每個測量時刻源節點發送一個有效數據包到匯聚節點所消耗能量的平均值。網絡生命周期為網絡中第一個節點能量消耗到小于最小能量時所用的時間。

經仿真測試，平均傳輸時延、平均丟包率和平均能量消耗分別如圖1～圖3所示，3種算法的網絡生命周期比較如表1所示。與AntWMSNs算法和ASAR算法相比，由于EBQR算法的目標函數中考慮了帶寬、時延、丟包率和能耗，在中間節點的轉移概率選擇時也考慮這些因素，并根據每次所得的目標函數值產生不同的揮發系數；同時，通過選取具有較高能量節點為通信節點，并選取整體能耗較小的路徑為傳輸路徑。由此尋找到的路徑性能值更好，傳輸數據時延、丟包率和能耗小。而ASAR算法在目標函數中雖考慮了帶寬、時延、丟包和能耗因素，但每個周期里所尋找的路徑很容易集中經過某個節點，從而導致該節點能量快速消耗殆盡。AntWMSNs算法在路徑選擇時通過比較節點的剩余能量，選擇剩余能量較大的節點作為下跳節點，但目標函數中丟包率和時延使用的是固定值，故尋找到的路徑時延和丟包率仍相對較大，測試結果證實了這點。由圖可知，EBQR算法的平均時延比ASAR算法低16.48 %，比AntWMSNs算法低18.89 %。EBQR算法的丟包率比ASAR算法和AntWMSN算法分別低23.22 %，22.83 %。EBQR算法的能耗比ASAR算法和AntWMSNs算法分別少1.912 5×10-4J,2.833 8×10-4J。EBQR算法的生命周期比ASAR算法和AntWMSNs算法分別延長了59 %和42.08 %。

圖1 平均傳輸時延Fig 1 Average transmission delay

圖2 平均丟包率Fig 2 Average packet loss rate

圖3 平均能量消耗Fig 3 Average energy consumption

算法本文算法ASAR算法AntWMSNs算法網絡生命周期(s)1175739827

4 結 論

在能量資源受限的WMSNs中，為滿足不同業務需求并充分考慮能量的高效使用，本文提出了一種EBQR算法。該算法將網絡帶寬、時延、丟包率和能量等因素作為目標函數，利用蟻群根據目標函數值的大小來動態調整信息素的揮發系數和信息素濃度增量，查找滿足不同QoS需求業務的最優路徑。仿真表明：與AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端時延降低了16 %，丟包率減少22 %，生命周期延長了近50 %，有效實現了網絡中節點能耗的均衡性。

[1] 陳志泊,徐孝成.一種改進的基于跳數的無線傳感器網絡路由算法[J].計算機科學,2013,40(4):83-85,114.

[2] Wang L,Ye W,Wang H,et al.Optimal node placement of industrial wireless sensor networks based onadaptive mutation probabi-lity binary particle swarm optimization algorithm[J].Computer Science and Information Systems,2012,9(4):1553-1576.

[3] 周 靈,王建新.無線多媒體傳感器網絡路由協議研究[J].電子學報,2011,39(11):149-156.

[4] 孫 巖,馬華東.無線多媒體傳感器網絡QoS保障問題[J].電子學報,2008,36(7):1412-1420.

[5] 段文軒.無線多媒體傳感器網絡服務質量的研究[D].泉州:華僑大學,2012:1-4.

[6] Cobo Luis,Quintero Alejandro,Pierre Samuel.Ant-based routing for wireless multimedia sensor networks using multiple QoS me-trics[J].Computer Networks, 2010, 54(17): 2991-3010.

[7] Kandris Dionisis,Tsagkaropoulos Michail,Politis Ilias,et al.Energy efficient and perceived QoS aware video routing over wireless multimedia sensor networks[J].Ad Hoc Networks,2011,9(4):591-607.

[8] 李 雪,賀昱曜,武奇生.一種WMSNs能量感知QoS路由機制設計[J].計算機工程與應用,2011,47(18):76-79.

[9] 黃 曼,程良倫.一種QoS保證的WMSNs實時路由協議[J].傳感器技術學報,2011,24(9):1341-1346.

[10] 李方敏,方藝霖,李 姮,等.無線多媒體傳感器網絡QoS區分服務路由機制[J].電子學報,2010,38(10):2322-2328.

[11] 孫 巖,馬華東,劉 亮.一種基于蟻群優化的多媒體傳感器網絡服務感知路由算法[J].電子學報,2007,35(4):705-711.

[12] 謝 慧,吳曉平,張用宇,等.多媒體傳感器網絡中基于ACO的QoS路由協議[J].海軍工程大學學報,2009,21(6):15-19.

[13] Yu Xiaohua,Luo Jiaxing,Huang Jinwen.An ant colony optimization-based QoS routing algorithm for wireless multimedia sensor networks[C]∥Int’l Conf on Communication Software and Networks(ICCSN),2011:37-41.

[14] 胡耀鋒,張建明,王新勝,等.能量感知的無線傳感器網絡多路徑路由研究[J].計算機工程與設計,2009,30(21):4811- 4814,4827.

[15] 吳華鋒,陳信強,毛奇凰,等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報,2013,34(4):165-170.

[16] 周明秀,程 科,汪正霞.動態路徑規劃中的改進蟻群算法[J].計算機科學,2013,40(1):314-316.

[17] 高 曼,劉以安,張 強.優化蟻群算法在反艦導彈航路規劃中的應用[J].計算機應用,2012,32(9):2530-2533,2541.

Energy-balanced QoS routing algorithms for WMSNs*

YANG Bing1,2, DENG Shu-guang2, WEN Shuang-chun1

(1.College of Information Science and Engineering,Hunan University,Changsha 410082,China;2.School of Communication and Electronic Engineering,Hunan City University,Yiyang 413000,China)

To guarantee demand of energy-constrained wireless multimedia sensor networks(WMSNs)multi-QoS,a kind of energy-balanced QoS routing(EBQR)algorithm is proposed.The algorithm through ant colony optimization to make the network bandwidth,time delay,packet loss rate and energy as objective function,and according to function value size dynamically adjust volatility coefficient and density increments of ant colony information element,provide the optimal path to meet different QoS needs in network businesses.Simulation results show that, compare with the AntWMSNs algorithm and the ASAR algorithm,average end-to-end time delay of EBQR algorithm is reduced 16 %,the packet loss rate is reduced 22 %,the life cycle lengthened nearly 50 %,effectively realize equilibrium of node energy consumption in the network.

wireless multimedia sensor networks(WMSNs); energy-balanced; quality of serivce(QoS) routing; ant colony algorithm

2013—08—15

湖南省科技計劃資助項目(2012FJ3025)； 湖南省教育廳科研基金資助項目(12C0585)

TP 212

A

1000—9787(2014)04—0122—03

楊 冰(1981-)，女，湖南益陽人，碩士研究生，講師，研究方向為車域自組網和無線傳感器網絡理論與優化。