基于QoS和分簇機制的WMSNs路由算法研究

杜佳軒,馬利亞,楊 軍

(1.寧夏大學 信息工程學院， 銀川 750021; 2.寧夏醫科大學 總醫院，銀川 750021;3.寧夏大學 計算機網絡管理中心， 銀川 750021)

基于QoS和分簇機制的WMSNs路由算法研究

杜佳軒1,馬利亞2,楊 軍3

(1.寧夏大學 信息工程學院， 銀川 750021; 2.寧夏醫科大學 總醫院，銀川 750021;3.寧夏大學 計算機網絡管理中心， 銀川 750021)

針對無線多媒體傳感器網絡中如何設計具有服務質量保證的路由算法問題，綜合考慮的了節點間標準化后的丟包率、延遲、剩余能量、可用存儲四個參數，提出算法ED-ACO(Energy and best distribution of Cluster Head Distance-Ant colony optimization);ED-ACO算法采用基于剩余能量和簇首最佳距離分布的分簇結構，均勻劃分網絡，將節點的丟包率，延遲，剩余能量，可用存儲標準化為具體參數，考慮到蟻群算法的狀態轉移概率公式中，利用該公式去選擇下一跳路徑傳送感知數據，同時滿足了服務質量要求;NS2仿真結果表明，與經典的AODV算法相比，在丟包率，延遲上保證了服務質量要求。

無線多媒體傳感器網絡；服務質量；最佳簇首分布；蟻群優化算法

0 引言

基于分簇的無線傳感器網路(WSNs)[1-2]的路由協議具有良好的擴展性，能更好的節省傳感器結點的資源，便于數據融合和傳輸。基于分簇的路由協議是將網絡劃分為若干簇，在一個簇內有一個簇頭結點和若干簇成員結點，簇頭對簇內成員進行信息采集，對數據進行融合轉發。LEACH[3]協議是一種經典的分簇協議，周期性的等概率選舉簇頭，使網絡的能量消耗相對均勻，從而延長網絡的生存期。但是LEACH由于等概率的選擇簇頭，所以網絡中簇頭分布不均勻，在選擇簇頭的過程中沒有考慮剩余能量和數據融合。EBUCBS[4]是一種基于扇形的能量均衡的非均勻分簇路由協議，采用固定分簇的方式減少重復分簇，且靠近基站的簇由于使用率高縮小簇的范圍，遠離基站的簇的范圍較大。QoS(Quality of Service)需求是區別于傳統傳感器網絡的一個重要特征，傳統WMSNs常以犧牲QoS來降低功耗.而無線多媒體傳感器網絡(WMSNs)則更加注重QoS，對于不同應用為多媒體數據流提供實時性、可靠性、帶寬、分組丟失等保障。REAR[5]是一種將鏈路帶寬和能量作為服務質量參數來設計的多媒體路由協議，使用元數據建立多路徑路由減少能量消耗，用一個代價函數來評估傳輸鏈路。Akkaya 等人[6]提出的由圖像傳感器節點組成的實時能量感知QoS路由協議，使用最小路徑代價找到多條網絡路由，但是算法的收斂性不高。HE[7]等人提出一種QoS路由協議SPEED，該方法提供了實時的端到端的時間保證，每個節點需要保存鄰居節點信息和利用地理信息轉發去尋找路徑。但是該算法沒有提供數據包的可靠傳輸保證。Felemban[8]等人提出一種多路徑多速度的MMSPEED算法，該算法將實時性和可靠性考慮到到路由算法上來作為QoS條件，但是因為沒有把能量效率考慮進來，所以只能適應于生存期較短的網絡。通過對蟻群算法的研究[9-10]，基于分簇思想，將結點的剩余能量，數據包頻率考慮作為參數，計算下一跳結點的轉發概率，在一定程度上也提高了數據的傳輸效率。

本文在結合分簇策略和服務質量保障機制下，將節點的丟包率，延遲，剩余能量，可用存儲標準化為具體參數，考慮到蟻群算法的狀態轉移概率公式中，利用該公式去選擇下一跳轉發路徑傳送感知數據，有效地保證了不同應用數據流的服務質量，增強了網絡的適用性。

1 網絡模型和問題描述

1.1 網絡模型

對于每路徑P的服務質量參數值計算如下：

(1)

(2)

(3)

(4)

對于具體環境下不同的應用有不同的服務質量要求，所以對于一條可行路徑PQoS∈P，目標函數:

為了簡化網絡模型，我們采取一些合理的假設如下：

1)有N個感知節點隨機地分布在M×M的方形區域。

2)基站位于網絡的外部且有無限的能量供應。

3)所有節點部署后沒有移動能力且有唯一的ID標識，均勻的部署在監測區域內。

4)所有節點初始能量相同，節點可以根據距離自適應的調整發射功率。

本文采用文獻[11]一致的無線電能耗模型，發送端的能量主要消耗在無線電發送元件和功率放大器，接收端的能量主要消耗在無線電發送元件，實驗采用自由空間(d2功耗損失)多徑衰減(d4功耗損失)信道模型，主要與發送端和接收端之間的距離有關。

傳感器節點發送l-bit數據耗能：

(5)

傳感器節點接受1-bit數據耗能：

(6)

1.2 問題描述

能量高效的分簇路由算法設計時應注意以下幾點：1)應該使用分布式的設計思想，可以有效利用節點的能量和提高網絡的生存期；2)簇的規模要適中，要考慮節點的負載均衡；3)要根據實際來設計應用相關的協議；4)感知節點之間的數據傳送應該采取分布式傳送，避免單跳傳送，應設計最短路徑的簇頭節點之間的數據傳輸協議，擴大網絡的生存期。分簇路由拓撲結構如圖1所示。

圖1 分簇路由拓撲結構

2 ED-ACO路由算法

ED-ACO是一種針對WMSNs設計的路由協議，是一種基于分簇結構的網絡，利用蟻群算法在源節點和Sink節點之間傳輸數據，在不同的應用環境下滿足不同服務質量要求。分簇階段我們采用剩余能量和最佳簇首距離的分簇方法，數據傳輸階段我們利用前向螞蟻和回溯螞蟻來尋找路徑和更新信息素軌跡，在這個過程中，我們將剩余能量、端到端的延遲，數據包的丟失率，可用的存儲空間作為服務質量參數來設計信息素更新公式，在選擇下一跳節點時，根據概率轉移公式，選擇具有最大概率的節點作為下一跳節點。在F-ant到達Sink節點后，Sink節點產生B-ant來更新節點的路由表和信息，當B-ant節點到達源節點后，開始傳輸數據，數據傳輸之后根據具體要求進行簇的調整和路由維持。具體的方案下文給出。

2.1 基于蟻群算法的路徑搜索

ED-ACO協議基于蟻群優化算法(AntColonyOptimization)去發現和維持簇頭節點到Sink節點或基站之間的路由。在分簇過程結束后路由發現算法開始執行。在提出路由發現算法之前，我們提出以下定義：

2.1.1 人工螞蟻結構

1)Ant.ID螞蟻的ID

2)Ant.Type在路由發現過程中的螞蟻類型。有轉發螞蟻F-ant,回溯螞蟻B-ant,路由維持螞蟻M-ant,數據螞蟻D-ant.

3)Ant.AllowedNode螞蟻節點，允許訪問的節點

4)Ant.hop螞蟻從簇頭源節點開始經過節點的條數，代表螞蟻的TTL。

5)Ant.info:各種類型的螞蟻使用此數據域存儲路由或節點的特殊信息，包括以下幾個子域：螞蟻所經過節點的最小剩余能量螞蟻經過的節點的累積隊列延遲、包的丟失率、節點的可用存儲。

在第一階段分簇之后，數據傳輸階段開始。首先簇首首先對簇內數據進行融合，然后數據以多跳的方式發送至目的節點，隨后非簇首節點進入休眠狀態以節約能量。多路徑搜索算法是基于蟻群算法模型，簇首節點產生前向螞蟻尋找到Sink節點的有效路徑，每個螞蟻都有自己的內存表，用禁忌表來記錄已經訪問過的節點，用Ant.AllowedNode域來記錄允許訪問的節點。ED-ACO算法中，前向螞蟻攜帶以下信息：數據包類型Type、所有的簇首節點ID、產生前向螞蟻的簇首節點ID、已訪問節點字段VisitedNode、螞蟻從源節點出發的時間SrcTime、跳數(螞蟻經過簇首節點個數)。后向螞蟻要攜帶數據包類型Type、已訪問節點字段VisitedNode，此后向螞蟻對應的前向螞蟻從源節點出發的時間SrcTime、鏈路最小剩余能量Emin、鏈路平均消耗能量Eavg。

表1 前向螞蟻攜帶的報文格式

表2 后向螞蟻攜帶的報文格式

2.1.2 信息素表

螞蟻信息素表是一種特殊的數據結構，存儲節點i經過簇頭鄰居j到Sink節點的路由信息素軌跡信息。存儲到節點的內存中，數據的組織結構如表3所示。

表3 節點i的信息素表

在表3中每一行表示對應特定的流量類型，由具體的應用實例定義。每一列是節點i的鄰居節點信息，主要包括四個值，每一個值是對于不同排隊類型下的信息素軌跡。分別是流量類型k下當前節點的剩余能量，延遲率，丟包率和可用存儲。

2.1.3 路由發現階段

當一個常規節點需要發送數據到Sink節點，這樣的信息要立即發送到它的簇頭，ED-ACO算法描述如下：當一個簇頭節點有感知數據需要發送，簇頭節點查找它的路由表為了找到合適的路徑傳送數據。在發起傳送數據開始時，簇頭源節點查找它的信息素表為了找到一個任意的沒有失效的節點信息。如果這個節點的時鐘大于一個截止時間那么這個信息失效，如果所有信息素表中的信息都失效，那么一個新的路由探測階段開始。大量的前向螞蟻需要被發送在路由探測階段。在路由發現過程結束后，緩存數據被立即發送到它的目的地。為了減少路由發現階段的延遲，ED-ACO算法在分簇階段后發起一個全路由探測階段，一個簇頭節點接受一個螞蟻過程如圖2所示。

圖2 ED-ACO的路由發現過程

ED-ACO算法有三個階段：轉發螞蟻階段、回溯螞蟻階段、路由維持階段。

轉發螞蟻階段：如果一個簇頭節點發現沒有期望的到達Sink節點的路徑，它將產生具體數量的轉發螞蟻(F-ants)去尋找通向Sink節點的路徑。轉發螞蟻作為一種代理去建立從CH節點到Sink節點的信息素軌跡，轉發螞蟻的結構上文中已經定義，F-ants的信息域攜帶：螞蟻經過的節點的最小剩余能量；每個螞蟻經過的節點的累積的隊列延遲，數據包的丟失率，可用的存儲空間。

這些參數作為服務質量(QoS)度量被用來在路由發現階段。為了找到一條源節點到Sink節點的路由，簇頭源節點廣播一個F-ant。螞蟻數據包在發送前必須預先定義，比如：ant.type=F-ant。ant.hopcount=0。簇頭源節點放入Ant.nallowed-nodes中，當中間的一個簇頭節點收到一個F-ant后，首先判斷接收到的F-ant 的Ant.nallowed-nodes域中是否存在回路，導致路由回路的螞蟻則被丟棄。在發送F-ant到下一個簇頭節點之前，F-ant的node.info關于當前簇頭的局部信息必須更新。更新規則如下：

energy←min(energy,re(ch))

delay←delay+del(ch)

packetloss←packetloss×pkl(ch)

memory←min(memory,mea(ch))

其中：re(ch)表示簇頭節點的剩余能量，dl(ch)表示鏈路的延遲率，pl(ch)表示簇頭節點之間的丟包率，ma(ch)表示簇頭節點的可用存儲空間。

(8)

式(8)中，啟發信息采用如下公式計算:

(9)

為了計算轉移概率值，必須計算下面這些概率值：

1)標準化的能量概率：

2)標準化的延遲概率：

3)標準化的包丟失概率：

4)標準化的可用內存的概率值：

最終，在流量類型k下從簇頭節點i到節點j的標準化的信息素值計算公式如下：

(10)

公式(8)計算了通過F-ant收集到了相關的QoS參數，能量，延遲，帶寬，數據包的丟失率，和可用存儲。標準化多個信息素值并轉化為相同的維度，以便計算轉移概率。路由發現過程中選擇下一跳通過參數alpha來控制不同信息素的權重達到不同的服務質量要求。

2.2 回溯螞蟻階段

當一個轉發螞蟻到達Sink節點，開始實施路由評估系統，通過將轉發螞蟻收集到的信息與具體應用設置的舒服質量參數值進行比較。例如，相關應用需要的路由是這樣的：包損失率小于1%，剩余能量高于80%。Sink節點來評估F-ants收集到的路由參數來決定路由是否有效。如果路由不滿足應用的服務質量要求，這個F-ants被丟棄。具體使用的應用必須調整這些參數為了獲得有效的路由，如果參數是不真實的或者不可能取得的在當前的網絡下，那么，Sink節點會丟棄這些螞蟻發現的所有路徑。

當一個F-ant被Sink節點接收，滿足當前應用的要求，Sink節點結束F-ant生命,一個B-ant產生。B-ant將F-ant收集到的信息以及路徑中的中間節點的ID用與F-ant相反的路徑發送。當中間簇頭節點i接收到一個B-ant,信息存儲在B-ant中用來更新相關路徑上的信息素，一輪結束后，增加已有路徑上的信息素，減少無關路徑上的信息素，使用信息素更新公式，計算公式如下：

1)能量信息素：

2)延遲信息素：

3)包丟失信息素：

4)可用內存信息素：

最優路徑上的信息素軌跡被增加，通過給一個信息素增量。此外，減少不好路徑上的信息素，使得螞蟻都遠離最壞的路徑。B-ant被發送到下一個簇頭通過與F-ant的相反路徑。當B-ant到達F-ant的源簇頭節點，在更新信息素軌跡后被丟棄。數據之后開始經過最大概率路徑傳送。

2.3 數據傳輸階段

在ED-ACO算法中，簇頭節點選擇具有最大信息素值的路徑轉發數據。對于一個給定的流量類型k，當一個節點有多個下一跳節點可以轉發數據，選擇具有最大ψ值的節點。這個ψ值的計算公式如公式(10)。這種策略可以讓數據根據預估計的鏈路質量有效的傳輸。當預估計的鏈路是良好的，接下來的工作由F-ant來完成，正如之前部分描述，具有負載均衡保證。當一個鏈路的質量比其他鏈路差，減少這條鏈路上的負載。其他的鏈路路徑則承擔更多的負載任務，為了避免擁塞，我們相應的調節QoS服務參數，使節點的能耗更加均勻，延長網絡生存期。

2.4 簇內調整

在第一輪數據傳輸結束后，要判斷路由經過的各簇首節點的能量水平，若簇首節點能量高于簇內平均剩余能量，保持原簇首不變；反之，進行簇內調整，根據公式選取高于平均剩余能量的節點當選簇頭，低于平均剩余能量的節點進入休眠狀態。新選出的簇首廣播原簇首ID、自身ID、自身剩余能量的消息通知簇內成員及其他簇首成員，所有簇首節點收到簇頭調整信息后更新各自對應的路由表信息。

3 仿真與分析

3.1 仿真實驗環境

本實驗采用NS2進行路由發現過程分析，我們從數據包的轉發率，端到端的延遲，路由開銷三個方面與AODV[12]協議進行對比，分析算法性能。實際仿真參數和文獻[13]基本相同如表4所示。

表4 仿真實驗的各個參數

3.2 路由過程

我們將改進的ED-ACO協議與經典的AODV協議相比較，在實驗中，使用參數如表1，主要從3個方面來對比算法的性能：數據包的轉發率、端到端的延遲、路由開銷。為了驗證算法的有效性，采用CBR流量模型產生32bytes到1024Bytes的數據包、多媒體數據包(1024Bytes)、標量數據包(32Bytes)。一個簇內的不同類型傳感器僅僅發送一次數據包到Sink節點。視頻節點的優先權高于標量節點。圖10所示為AODV協議的包轉發率，ED-ACO協議標量數據的轉發率和多媒體數據包的轉發率。不同的參數設置如下：

對于ED-ACO-S(標量數據)α=0,αe=1，最小剩余能量必須大于0，ED-ACO-M(視頻數據)α=0,αε=1，對于視頻數據包的損失率必須最小。

在所有流量類型下信息素的蒸發率ρ都為0.7。

從圖3中可以發現，在實驗開始時候，ED-ACO-S與AODV轉發率都比較高，但是運行一段時間后，ED-ACO-M轉發率遠遠高于ED-ACO-S和AODV。這是因為在開始階段ED-ACO-M缺少足夠的信息去發現有效的路徑，但是經過一段時間，隨著算法收斂，有效路徑上的信息素增多，找到最優路徑傳輸數據，數據包的轉發因而提高。因此實驗結論與我們的假設是一致的。

圖3 數據包的轉發率對比圖

在圖4中我們觀察兩個協議端到端的平均時延，在實驗中，我們設置參數如下，α=0,αδ=1(αδ為累計隊列延遲參數)。通過圖4我們可以觀察到ED-ACO-M和ED-ACO-S的端到端的延遲要比AODV協議要小，因為多路徑的發現，當到達Sink節點的路徑失效，數據包會立即使用其他路徑傳輸而不用進行路由發現階段，因此有效地減少了短刀段的延遲。在ED-ACO-S中，路由發現階段主要考慮了剩余能量，所以不會把數據包都轉發到最好的路徑上，所以ED-ACO-S的延遲要比ED-ACO-M要高。

圖4 端到端的延遲對比圖

如圖5所示，因為要周期性的去監測和維持路由所需條件產生了大量的F-ANT和B-ANT，所以ED-ACO的路由開銷要大于AODV協議。

圖5 路由開銷對比圖

4 結束語

無線傳感器網絡是應用相關的網絡，數據采集是其主要的功能，采用分簇路由技術可以均衡的減少能量消耗，擴大網絡生存期。本文采用分簇結構，利用蟻群優化算法在各簇頭之間找到一條最短路徑多跳傳輸數據，減少了數據傳送距離。通過大量的模擬實驗證明了ED-ACO協議在分簇方面良好的性能，有效地減少了因數據傳送消耗的能量，最終在一定程度上延長了網絡的生存期，保證了服務質量。

[1] Abbasi A A, Younis M. A survey on clustering algorithms for wireless sensor networks[J]. Computer Communications, 2007, 30 (14/15): 2826-2841.

[2] 張軍強, 王汝傳, 黃海平. 基于分簇的無線多媒體傳感器網絡數據聚合方案研究[J]. 電子與信息學報, 2014, (01): 8-14.

[3] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on wireless communications, 2002, 1 (4): 660-670.

[4] 劉同來, 劉偉強. 無線傳感器網絡中基于扇形的非勻均分簇路由協議[J]. 微電子學與計算機, 2015(2): 100-104.

[5] Lan Y, Wenjing W, Fuxiang G. A real-time and energy aware QoS routing protocol for multimedia wireless sensor networks[A].IEEE[C]. 2008: 3321-3326.

[6] Akkaya K, Younis M. Energy and QoS aware routing in wireless sensor networks[J]. Cluster computing, 2005, 8 (2/3): 179-188.

[7] He T, Stankovic JA, Lu C,et al. SPEED: A stateless protocol for real-time communication in sensor networks[C]: IEEE, 2003: 46-55.

[8] Felemban E, Lee C G, Ekici E. MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J]. IEEE transactions on mobile computing, 2006, (6): 738-754.

[9] 鄧 達, 周激流, 林 鋒. 基于蟻群算法的無線多媒體傳感器網絡路由研究[J]. 北京理工大學學報, 2011(4): 456-460.

[10] 劉 逵, 劉三陽, 馮海林,等. 一種基于分簇蟻群策略的無線傳感器網絡路由算法[J]. 控制與決策, 2012(6): 929-932,936.

[11] Khediri S E, Nasri N, Wei A,et al. A new approach for clustering in wireless sensors networks based on LEACH[J]. Procedia Computer Science, 2014, 32: 1180-1185.

[12] 周德榮. 基于蟻群算法改進的AODV路由協議研究[J]. 西南師范大學學報(自然科學版), 2014(11): 75-80.

[13] 李芳芳, 王 靖. 一種基于LEACH協議的無線傳感器網絡路由算法[J]. 傳感技術學報, 2012(10): 1445-1451.

Research on Wireless Multimedia Sensor Networks ant Colony Routing Algorithm Based on QoS and Clustering

Du Jiaxuan1，Ma Liya2，Yang Jun3

(1.School of Information Engineering， Ningxia University，Yinchuan 750021，China;2.General Hospital, Ningxia Medical University, Yinchuan 750021，China;3.Network Administrator Center, Ningxia University，Yinchuan 750021，China)

Aiming at the wireless multimedia sensor networks of QoS routing problem, this paper proposed a ED-ACO(Energy and best distribution of Cluster Head Distance-Ant colony optimization ) taking nodes statistics parameters ,packet loss, delay ratio, remain energy and available memory into consideration. ED-ACO used the clustering structure based on energy and best distribution of cluster head distance to partition networks uniformly, selecting the next hop to transmit sensor data according to the equation of state transition, in the same time it met the QoS requirements in WMSNs. NS2 simulation results indicates that ED-ACO compared with AODV satisfies the QoS requirements in packet loss ratio and delay ratio.

WMSNs；QoS；best cluster head distribution；ACO

2016-09-17；

2016-10-10。

國家自然科學基金項目(61261001)。

杜佳軒(1990-)，男，寧夏吳忠人，碩士，主要從事無線傳感網方向的研究。

楊 軍(1972-)，男，寧夏銀川人，博士，教授，CCF會員，主要從事無線傳感網方向的研究。

1671-4598(2017)02-0196-05

10.16526/j.cnki.11-4762/tp.2017.02.054

TP393.1

A