無線多媒體傳感器網絡視頻流區分服務多徑Qos路由算法

何建新 ?k賈麗媛

摘要：無線多媒體傳感器網絡視頻流傳輸需要提供多樣性QoS保障，傳統的無線傳感器網絡路由協議不能很好地保證多媒體視頻流數據傳輸，改進多徑路由算法TPGF下一跳節點選擇方法，提出一種適合視頻流傳輸的區分服務多路徑Qos路由算法DSMQRA。綜合考慮各路徑跳數與節點剩余能量情況，在源節點與匯聚節點間找到多條優化的節點不相交路徑；采用區分服務機制，重點保護視頻流關鍵幀，提高視頻流傳輸質量。在NS2環境下與AODV、GPSR、TPGF等算法進行仿真對比分析，實驗結果表明DSMQRA算法能夠有效延長網絡生存時間、降低丟包率、減小幀延時、圖像峰值信噪比較高，更加適合無線多媒體傳感器網絡視頻流數據傳輸。

關鍵詞：無線多媒體傳感器網絡；區分服務；多徑路由；算法

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

1引言

無線多媒體傳感器網絡（WMSNs）通過集成于節點上的CMOS攝像頭、微型麥克風等多媒體傳感器協作地感知外部環境，從物理環境中采集圖像、視頻、音頻等多媒體信息，實現對監測區域更細粒度的精確監測。視頻流傳輸是WMSNs的典型應用，視頻傳感器節點將采集的視頻數據多跳傳輸至sink匯聚節點。為了保障視頻流傳輸質量，延長網絡生存時間，必須考慮流媒體數據對帶寬、時延、抖動、丟包率、能耗等QoS指標的嚴格要求，必須考慮全網能量的均衡消耗。

經典的AODV[1]路由協議，具有按需路由、操作簡單、可擴展性好等優點，但卻沒有考慮路由負載，存在冗余消息多、協議開銷大的缺點。近年來提供QoS保障的多徑路由算法日益成為WMSNs的研究熱點[2-3]。TPGF[4]（Two-phasegeographicGreedyForwardingroutingalgorithm）基于地理位置信息采用貪婪策略在鄰居節點集中選擇距離目的節點最近的節點作為下一跳，直到找到一條可能路徑，然后基于最小跳數進行路徑優化，但是其下一跳節點選擇僅考慮了距離因素，沒有考慮節點能量因素，一旦路徑上任意節點能量耗盡，該路徑將癱瘓，這時最短路徑便成為了最不安全的路徑。

隨著研究的不斷深入，出現了專門針對多媒體數據傳輸的路由機制。利用視頻失真預測模型，Kandris等人設計了QoS路由算法PEMuR[5]，其缺點在于失真預測需要額外計算開銷，并不適用資源受限的傳感器網絡。為了增強網絡整體吞吐量，YahyaB等提出了基于服務區分的多路徑QoS路由協議EQSR[6]，通過區分不同服務數據將較為重要的數據通過分片編碼方式分散到多條路徑中傳輸，但對數據重新編碼同樣增加了網絡的額外開銷。對視頻數據進行有效編碼能夠壓縮原始視頻的數據量，且經過編碼后的視頻數據具有不同重要性，如MPEG-4編碼方式[7]，其GOP（groupofpicture）格式為IPBBPBBPIP……，其中I幀是關鍵幀，P幀與B幀是非關鍵幀，P幀與B幀的解碼依賴于I幀，如果I幀出錯，將導致接收端P幀、B幀無法解碼而成為無用數據，這樣不僅影響視頻解碼質量，而且造成網絡資源浪費。本文改進TPGF下一跳節點選擇方法，依據編碼后不同數據幀的重要程度采用區分服務方法，提出一種適合視頻流傳輸的區分服務多路徑Qos路由算法DSMQRA（DifferentiatedServicesMultipathQoSRoutingAlgorithm），綜合考慮距離與能量因素，使每條路由成為能量感知路由，同時采用區分服務機制重點保護視頻流I關鍵幀，提高視頻數據傳輸質量。

2網絡模型

無線多媒體傳感器網絡拓撲可抽象成帶權有向圖G=（V，E），其中V={v1，v2，…，vn}為有限傳感器節點集合，節點個數n=|V|；E={e1，e2，…，em}為單跳通信鏈路集合。對于任意鏈路e∈E，有e=（vi，vj），vi∈V，vj∈V，i≠j。網絡模型其它特征如下：

1）每條鏈路具有帶寬、時延、丟包率等QoS特征值。帶寬即鏈路數據傳輸速率；時延主要由中繼節點排隊時延與鏈路傳輸時延組成；丟包率包括節點緩沖區溢出丟包與信道間干擾丟包。

2）基站隨機部署，每個傳感器節點和基站位置相對固定，采用GPS獲得節點位置信息。假設一跳以內每個節點都有鄰居節點，并且每個節點都知道自己位置信息。

3）每個傳感器節點分為活節點可用、活節點不可用、死節點三種不同狀態。活節點可用表示節點能量充足，可用于正常數據采集和傳輸，狀態設置為1；死節點表示節點因能量耗盡而死亡，狀態設置為-1；活節點但不可用表示節點被設置成阻塞節點，狀態設置為0。當出現以下情況，節點將被設置成阻塞節點：①除上一跳節點外，再無其他節點可以選擇作為其一跳以內的鄰居節點；②除上一跳節點外，其他一跳以內的鄰居節點已經被其他路徑占用；③出現路由環路時，路由環路起點處的傳感器節點將其下一跳節點置為阻塞節點。

3視頻流區分服務多徑QoS路由算法

3.1鄰居節點表建立

每個節點定期通過洪泛方式向其一跳范圍內所有鄰居節點廣播節點ID、坐標、剩余能量等自身信息，節點根據收到的信息建立或更新如圖1所示的鄰居節點表，其中剩余能量初值為系統初始化時預設的節點能量，節點狀態初始值為1，表示活節點可用；節點被路徑所占用時，所在路徑號為從0開始的自然數，路徑號初始值為-1。

節點ID坐標剩余能量節點狀態所在路徑號圖1鄰居節點表

當節點收到鄰居節點數據包時將按以下步驟建立和更新鄰居節點表信息，首先提取節點ID，然后查找其自身鄰居節點表，并按以下三種情況處理：①若已經存在該節點，則更新該鄰居節點表信息后丟棄該數據包；②若不存在該節點，則將其加入鄰居節點表；③若大于預先設定時間間隔仍未收到節點更新數據包信息，則從鄰居節點表項中刪除該節點信息。

3.2多徑路由的建立

源節點至匯聚節點間維護多條路徑，可減少節點之間由于帶寬資源有限而導致的沖突，有效緩解網絡擁塞，延長網絡生存周期，提高網絡吞吐量。多徑路由建立包括貪心轉發和路徑優化兩個階段。endprint

3.2.1貪心轉發階段

源節點向匯聚節點發送Hello探索數據包，采用貪心轉發和回溯方法，建立從源節點至匯聚節點的多條路徑。

1）貪心轉發

TPGF采取貪心轉發策略，從源節點發送探索數據包開始，總是從鄰居節點集中選擇距sink節點最近的節點作為下一跳，直到匯聚節點為止，但最優節點選擇并沒有考慮節點的剩余能量情況。DSMQRA改進了TPGF下一跳節點選擇方法，綜合考慮節點距離因素和能量因素，使整條路由成為能量感知路由。DSMQRA選擇最優節點的標準是按公式（1）計算估計代價值C（n，d），其值最小的節點被選擇為下一跳節點。考慮距離、能量變化敏感度，引入指數加權移動平均EWMA，平滑估計代價值大小，減少瞬時突發采樣對估計代價值影響。

C（n，d）=（1-λ）*d（n，d）+λ*e（n），（0<λ<1）（1）

其中d（n，d）表示本節點到目標節點的距離，計算如公式（2）所示。

d（n，d）=d2（i，d）-d2mind2max-d2min（2）

公式（2）中d（i，d）為鄰居節點i距離匯聚節點sink的距離，dmin為所有鄰居節點距離匯聚節點距離最小值，dmax為所有鄰居節點距離匯聚節點距離最大值。

公式（1）中e（n）表示鄰居節點剩余能量大小，e（n）計算如公式（3）所示，其中Einit為節點初始能量，Eres為節點當前剩余能量。

e（n）=Einit-EresEinit（3）

公式（1）中權值λ隨網絡動態變化，網絡初始化時，所有節點剩余能量均相同，估計代價值僅與距離d（n，d）有關，此時λ值等于零；隨著網絡數據傳輸，各節點因負載不同導致能量消耗不同，鄰居節點間剩余能量水平差異變大，此時剩余能量部分在估計代價中權重應該逐漸加大，而距離部分權重將相應減少。權值λ采用歸一化處理后如公式（4）所示，其中Eres_max表示所有鄰居節點剩余能量最大值，Eres_min表示所有鄰居節點剩余能量最小值。

λ=Eres_max-Eres_minEres_max（4）

2）回溯

當傳感器節點因能量耗盡成為死節點時將產生路由空洞。DSMQRA算法采用“回溯”方法避免當前節點遇到路由空洞而造成路由探測失敗。“回溯”即當前節點除上一跳節點外，其一跳鄰居節點表中沒有可用的下一跳節點時，在鄰居節點表中將該節點設置成阻塞節點，且節點狀態置0，表示該節點為“活節點不可用”，然后回退至上一跳節點，從而繞開路由空洞，并按（1）式重新計算選擇下一跳鄰居節點。

3.2.2路徑優化階段

源節點至匯聚節點間新路由發現后，根據鄰居節點表信息，路徑中每個節點分別被標上路徑號和節點序號標簽，但路徑中可能存在“路徑環”，即路徑中出現兩個或兩個以上節點是另一個節點的鄰居，如圖2中的路徑環ABC。DSMQRA算法采用“標簽優化”方法消除路徑環，即單徑路由形成后，匯聚節點會有一確認信息通過反向路由回送給源節點，為了消除路徑環，規定路徑中節點只給具有相同路徑號、序號較小的一跳鄰居節點發送確認信息，如圖2所示，C節點標簽1：2表示路徑1上序號為2的節點，當節點C回送確認信息時，將選擇序號較小的節點A，而不再選擇節點B，將B節點設為活節點且可用，狀態置1，這樣B節點被釋放作為下一次建立新路徑時的備用節點，從而形成A-C-D-E-F-S的優化路徑。重復上述貪心轉發和路徑優化過程，直到找到所有從源節點到目標節點的優化不相交路徑，并在源節點中存儲每條路徑的跳數，作為路由選擇的依據。最先建立的路徑，跳數較少，能量最充足，便成為最優路徑，后續建立的路徑優先級將依次遞減。

3.3視頻流編碼與傳輸

為了提高視頻數據的傳輸質量，應用層視頻編碼器采用MPEG-4編碼方式將視頻數據進行壓縮編碼，為數據包分別打上I、P、B幀標識，幀標識作為層間交互信息傳遞給網絡層，如圖3所示。

為了提高視頻數據的傳輸質量，使解碼端能夠較好的恢復視頻，網絡層將編碼后的視頻數據采用多路徑方式傳輸，根據數據包所屬幀的重要程度不同，運用區分服務方法，選擇跳數少、能量消耗小、有QoS保障的最優路徑傳輸I關鍵幀，選擇次優路徑傳遞P幀、B幀等非關鍵幀，從而實現對I關鍵幀的重點保護。

3.4區分服務機制

一般情況下路徑長度越短、能量越充足，其QoS保障水平越高。綜合考慮距離與能量因素，DSMQRA算法根據公式（5）計算估計代價值cost（H，E）大小實現區分服務。估計代價是路徑長度和整條路徑能耗的加權和，其中H為路徑跳數歸一化值，E為能量消耗歸一化值，μ為權值（0<μ<1）。當μ一定時，跳數少、能量消耗小，估計代價值越小，該路徑Qos保障級別越高，將被選擇用來傳輸I關鍵幀，然后選擇次優路徑傳遞P幀、B幀等非關鍵幀。

cost（H，E）=（1-μ）*H+μ*E（5）

路徑跳數H的歸一化值由（6）式決定，其中hop（i）表示路徑i自身包含的跳數，∑hop表示源節點至匯聚節點所有路徑的跳數之和。

H=hop（i）∑hop（6）

一般情況下路徑傳輸數據包數量越小，能量消耗越少，剩余能量值越大，該路徑被選中的可能性越大。由于路徑中節點剩余能量難以精確估計，能量消耗E將用該條路徑所傳輸數據包個數來估計，公式（5）中E的值由（7）式決定，其中num（i）表示路徑i所傳輸數據包數量，∑num表示所有路徑傳輸數據包數量之和。

E=num（i）∑num（7）

在視頻傳輸初期能量充足，估計代價值計算主要考慮路徑長度，隨著視頻流傳輸，節點剩余能量將逐漸減少，此時跳數少的路徑不一定是最佳路徑，能耗因素的權值應該逐漸增大。因此綜合考慮路徑跳數和能耗因素，公式（5）中權值μ的選取可以采用（8）式所示的雙曲正切函數。endprint

μ=1-exp（（-2）*∑num）1+exp（（-2）*∑num）（8）

雙曲正切函數圖像如圖4所示，μ在區間[0，1]之間變化，隨著所傳輸數據包個數num的增大，μ值趨近于1，此時估計代價值計算將重點考慮能耗因素。

4仿真與結果分析

4.1仿真環境設置

將DSMQRA算法加入NS2[8]模擬器核心組件，添加Evalvid[9]視頻質量評價工具集，并與TPGF、GPSR[10]（GreedyPerimeterStatelessRouting）、AODV（AdhocOndemandDistanceVectorRouting）等算法性能進行仿真比較。highway.yuv視頻測試用例包含2000幀，其中I幀223，P幀445，B幀1332，采用MPEG-4編碼格式，每幀圖像176*144像素，發送速率25幀/秒；根據不同節點數分為60、80、……200等八種不同網絡場景，針對每種場景分別測試不同算法作用下的網絡生存時間、丟包率、I幀丟幀率、圖像峰值信噪比PSNR等性能指標。其它仿真實驗參數設置如表1所示。

網絡覆蓋區域（600*400）m2節點傳輸半徑100m源節點坐標（500，300）sink節點坐標（100，100）普通節點能量J源節點匯聚節點能量30J接收功率0.4W數據包最大值1000B發送功率0.4W節點分布模式隨機4.2結果及分析

1）網絡生存時間比較

網絡生存時間為從WMSNs初始部署到第一個節點能量耗盡失去傳感能力的時間段。如圖5所示為不同場景網絡生存時間比較。

節點數量（個）圖5網絡生存時間比較

DSMQRA算法將網絡負載選擇多路徑傳輸，更多節點進行分攤，具有更好的負載均衡性，比采用單路徑傳輸的GPSR和AODV的網絡生存周期更長，這對于數據量較大的WMSNs來說非常關鍵；綜合考慮距離與能量因素，同時采用區分服務機制的DSMQRA比TPGF具有更長的網絡生存期，表明采用區分服務機制可進一步在多路徑間均衡網絡負載，延長網絡生存時間。隨著網絡場景節點數增加，節點鄰居數目增多，因為節點周期性維護其鄰居節點表信息所消耗能量也將隨之升高，所以網絡生存時間曲線略有下降。

2）丟包率比較

不同網絡場景丟包率比較如圖6所示。當網絡規模較小時（小于120節點），由于節點密度較小，不能提供足夠多冗余節點來實現多路徑傳輸，當發生節點死亡時，導致網絡性能驟減，此時DSMQRA算法丟包率比GPSR和AODV略大。但當節點數達到一定規模（大于120節點）時，DSMQRA算法保證路徑有一定冗余度，當某條路徑失效時，將通過冗余路由均衡網絡負載、保障傳輸可靠性，大大減少由網絡擁塞帶來的數據包丟失情況。

節點數量（個）圖6丟包率比較

3）I幀丟幀率比較

在解碼端I關鍵幀對于視頻能否正確解碼最為重要。如圖7所示為不同場景I幀丟幀率比較。當網絡規模較小時，還不能實現多路徑傳輸，DSMQRA算法I幀丟幀率較高；隨著網絡規模增大，一方面由于改進的多路徑傳輸均衡了網絡負載，另一方面采用區分服務機制對I關鍵幀實現了重點保護，I幀丟幀率明顯低于TPGF、GPSR和AODV。4）圖像峰值信噪比PSNR比較

解碼后的圖像質量可通過如圖8所示的平均峰值信噪比PSNR來反映，PSNR值越大代表圖像失真越少。當網絡規模小、節點密度較低時，因沒有足夠的冗余節點，當路徑上有節點死亡時，路徑很難完成自愈，此時DSMQRA的PSNR值較小。隨著節點密度變大，TPGF因采用多路徑傳輸方式，PSNR值變大，說明圖像質量有所改善。DSMQRA綜合考慮了節點剩余能量和多路徑聚集程度，均衡了負載和能耗避免了網絡擁塞，同時采用區分服務機制對視頻流I關鍵幀傳輸進行了最高優先級保障，此時的PSNR值變得最大，表明解碼后的圖像質量最佳。

5結論

本文提出的DSMQRA算法，在網絡規模與節點密度較大的WMSNs中經過與GPSR、AODV、TPGF進行仿真對比，表現出了更好的網絡性能。該算法主要是在能量約束條件下提出的，視頻的QoS保障只局限于網絡層和應用層協作，實際的WMSNs路由是在能量、時延、可靠性和安全性等多約束條件下進行的。因此，設計滿足多約束條件，實現其他各層和網絡層跨層協作的無線多媒體傳感器網絡路由算法，達到整個網絡節能效果最優化，是我們在此基礎上應該進一步深入研究的問題。

參考文獻

[1]C.Perkins，E.BeldingRoyer.RFC3561，AdHoconDemandDistanceVector（AODV）Routing[S].2003.

[2]周靈，王建新.無線多媒體傳感器網絡路由協議研究[J].電子學報，2011，39（1）：149-156.

[3]董武世，柯宗武，陳年生.無線多媒體傳感器網絡的QoS路由算法[J].武漢理工大學學報：交通科學與工程版，2009，33（4）：783-786.

[4]LeiShu，YanZhang.Geographicroutinginwirelessmultimediasensornetworks[C].Proceedingsofthe2thIEEEInternationalConferenceonFutureGenerationCommunicationandNetwork.HainanIsland：IEEECommunicationSociety，2008，12.68-73.

[5]KANDRISD，TSAGKAROPOULOSM，POLITISI，TZESA，KOTSOPOULOSS.EnergyefficientandperceivedQoSawarevideoroutingoverwirelessmultimediasensornetworks[J].AdHocNetworks，2011，9（4）：591-607.

[6]YAHYAB，BenOthmanJ.AnenergyefficientandQoSawaremultipathroutingprotocolforwirelesssensornetworks[C].InProc.oftheIEEE34thConf.onLocalComputerNetworks.Zurich：BBNTechnologies，2009.93-100.

[7]樊曉平，熊哲源，陳志杰等.無線多媒體傳感器網絡視頻編碼研究[J].通信學報，2011，32（9）：137-144.

[8]于斌，孫斌，溫暖，等.NS2與網絡模擬[M].北京：人民郵電出版社，2007.

[9]柯志亨，程榮祥，鄧德雋.NS2仿真試驗——多媒體和無線網絡通信[M].北京：電子工業出版社，2009.

[10]KARPB，KUNGH.GreedyPerimeterStatelessRouting（GPSR）[C].InProc.ofthe6thInternationalConferenceonMobileComputingandNetworking[C].Boston：Massachusetts，2000：243-25.

第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016

收稿日期：2015-08-04

基金項目：國家級“電子信息工程”專業綜合改革試點專業項目（高教司函[2013]5號）；湖南省教育廳開放基金項目（15K051）endprint