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

杜佳軒,馬利亞,楊 軍

(1.寧夏大學(xué) 信息工程學(xué)院， 銀川 750021; 2.寧夏醫(yī)科大學(xué) 總醫(yī)院，銀川 750021;3.寧夏大學(xué) 計算機(jī)網(wǎng)絡(luò)管理中心， 銀川 750021)

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

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

(1.寧夏大學(xué) 信息工程學(xué)院， 銀川 750021; 2.寧夏醫(yī)科大學(xué) 總醫(yī)院，銀川 750021;3.寧夏大學(xué) 計算機(jī)網(wǎng)絡(luò)管理中心， 銀川 750021)

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

無線多媒體傳感器網(wǎng)絡(luò)；服務(wù)質(zhì)量；最佳簇首分布；蟻群優(yōu)化算法

0 引言

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

本文在結(jié)合分簇策略和服務(wù)質(zhì)量保障機(jī)制下，將節(jié)點的丟包率，延遲，剩余能量，可用存儲標(biāo)準(zhǔn)化為具體參數(shù)，考慮到蟻群算法的狀態(tài)轉(zhuǎn)移概率公式中，利用該公式去選擇下一跳轉(zhuǎn)發(fā)路徑傳送感知數(shù)據(jù)，有效地保證了不同應(yīng)用數(shù)據(jù)流的服務(wù)質(zhì)量，增強(qiáng)了網(wǎng)絡(luò)的適用性。

1 網(wǎng)絡(luò)模型和問題描述

1.1 網(wǎng)絡(luò)模型

對于每路徑P的服務(wù)質(zhì)量參數(shù)值計算如下：

(1)

(2)

(3)

(4)

對于具體環(huán)境下不同的應(yīng)用有不同的服務(wù)質(zhì)量要求，所以對于一條可行路徑PQoS∈P，目標(biāo)函數(shù):

為了簡化網(wǎng)絡(luò)模型，我們采取一些合理的假設(shè)如下：

1)有N個感知節(jié)點隨機(jī)地分布在M×M的方形區(qū)域。

2)基站位于網(wǎng)絡(luò)的外部且有無限的能量供應(yīng)。

3)所有節(jié)點部署后沒有移動能力且有唯一的ID標(biāo)識，均勻的部署在監(jiān)測區(qū)域內(nèi)。

4)所有節(jié)點初始能量相同，節(jié)點可以根據(jù)距離自適應(yīng)的調(diào)整發(fā)射功率。

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

傳感器節(jié)點發(fā)送l-bit數(shù)據(jù)耗能：

(5)

傳感器節(jié)點接受1-bit數(shù)據(jù)耗能：

(6)

1.2 問題描述

能量高效的分簇路由算法設(shè)計時應(yīng)注意以下幾點：1)應(yīng)該使用分布式的設(shè)計思想，可以有效利用節(jié)點的能量和提高網(wǎng)絡(luò)的生存期；2)簇的規(guī)模要適中，要考慮節(jié)點的負(fù)載均衡；3)要根據(jù)實際來設(shè)計應(yīng)用相關(guān)的協(xié)議；4)感知節(jié)點之間的數(shù)據(jù)傳送應(yīng)該采取分布式傳送，避免單跳傳送，應(yīng)設(shè)計最短路徑的簇頭節(jié)點之間的數(shù)據(jù)傳輸協(xié)議，擴(kuò)大網(wǎng)絡(luò)的生存期。分簇路由拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 分簇路由拓?fù)浣Y(jié)構(gòu)

2 ED-ACO路由算法

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

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

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

2.1.1 人工螞蟻結(jié)構(gòu)

1)Ant.ID螞蟻的ID

2)Ant.Type在路由發(fā)現(xiàn)過程中的螞蟻類型。有轉(zhuǎn)發(fā)螞蟻F-ant,回溯螞蟻B-ant,路由維持螞蟻M-ant,數(shù)據(jù)螞蟻D-ant.

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

4)Ant.hop螞蟻從簇頭源節(jié)點開始經(jīng)過節(jié)點的條數(shù)，代表螞蟻的TTL。

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

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

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

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

2.1.2 信息素表

螞蟻信息素表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，存儲節(jié)點i經(jīng)過簇頭鄰居j到Sink節(jié)點的路由信息素軌跡信息。存儲到節(jié)點的內(nèi)存中，數(shù)據(jù)的組織結(jié)構(gòu)如表3所示。

表3 節(jié)點i的信息素表

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

2.1.3 路由發(fā)現(xiàn)階段

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

圖2 ED-ACO的路由發(fā)現(xiàn)過程

ED-ACO算法有三個階段：轉(zhuǎn)發(fā)螞蟻階段、回溯螞蟻階段、路由維持階段。

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

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

energy←min(energy,re(ch))

delay←delay+del(ch)

packetloss←packetloss×pkl(ch)

memory←min(memory,mea(ch))

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

(8)

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

(9)

為了計算轉(zhuǎn)移概率值，必須計算下面這些概率值：

1)標(biāo)準(zhǔn)化的能量概率：

2)標(biāo)準(zhǔn)化的延遲概率：

3)標(biāo)準(zhǔn)化的包丟失概率：

4)標(biāo)準(zhǔn)化的可用內(nèi)存的概率值：

最終，在流量類型k下從簇頭節(jié)點i到節(jié)點j的標(biāo)準(zhǔn)化的信息素值計算公式如下：

(10)

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

2.2 回溯螞蟻階段

當(dāng)一個轉(zhuǎn)發(fā)螞蟻到達(dá)Sink節(jié)點，開始實施路由評估系統(tǒng)，通過將轉(zhuǎn)發(fā)螞蟻收集到的信息與具體應(yīng)用設(shè)置的舒服質(zhì)量參數(shù)值進(jìn)行比較。例如，相關(guān)應(yīng)用需要的路由是這樣的：包損失率小于1%，剩余能量高于80%。Sink節(jié)點來評估F-ants收集到的路由參數(shù)來決定路由是否有效。如果路由不滿足應(yīng)用的服務(wù)質(zhì)量要求，這個F-ants被丟棄。具體使用的應(yīng)用必須調(diào)整這些參數(shù)為了獲得有效的路由，如果參數(shù)是不真實的或者不可能取得的在當(dāng)前的網(wǎng)絡(luò)下，那么，Sink節(jié)點會丟棄這些螞蟻發(fā)現(xiàn)的所有路徑。

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

1)能量信息素：

2)延遲信息素：

3)包丟失信息素：

4)可用內(nèi)存信息素：

最優(yōu)路徑上的信息素軌跡被增加，通過給一個信息素增量。此外，減少不好路徑上的信息素，使得螞蟻都遠(yuǎn)離最壞的路徑。B-ant被發(fā)送到下一個簇頭通過與F-ant的相反路徑。當(dāng)B-ant到達(dá)F-ant的源簇頭節(jié)點，在更新信息素軌跡后被丟棄。數(shù)據(jù)之后開始經(jīng)過最大概率路徑傳送。

2.3 數(shù)據(jù)傳輸階段

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

2.4 簇內(nèi)調(diào)整

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

3 仿真與分析

3.1 仿真實驗環(huán)境

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

表4 仿真實驗的各個參數(shù)

3.2 路由過程

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

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

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

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

圖3 數(shù)據(jù)包的轉(zhuǎn)發(fā)率對比圖

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

圖4 端到端的延遲對比圖

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

圖5 路由開銷對比圖

4 結(jié)束語

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

[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] 張軍強(qiáng), 王汝傳, 黃海平. 基于分簇的無線多媒體傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合方案研究[J]. 電子與信息學(xué)報, 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] 劉同來, 劉偉強(qiáng). 無線傳感器網(wǎng)絡(luò)中基于扇形的非勻均分簇路由協(xié)議[J]. 微電子學(xué)與計算機(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] 鄧 達(dá), 周激流, 林 鋒. 基于蟻群算法的無線多媒體傳感器網(wǎng)絡(luò)路由研究[J]. 北京理工大學(xué)學(xué)報, 2011(4): 456-460.

[10] 劉 逵, 劉三陽, 馮海林,等. 一種基于分簇蟻群策略的無線傳感器網(wǎng)絡(luò)路由算法[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] 周德榮. 基于蟻群算法改進(jìn)的AODV路由協(xié)議研究[J]. 西南師范大學(xué)學(xué)報(自然科學(xué)版), 2014(11): 75-80.

[13] 李芳芳, 王 靖. 一種基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)路由算法[J]. 傳感技術(shù)學(xué)報, 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。

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

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

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

1671-4598(2017)02-0196-05

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

TP393.1

A