基于改進(jìn)ACO與分布式社區(qū)檢測(cè)的WSN路由協(xié)議

朱利民，趙 麗

1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，河南 新鄉(xiāng) 453000

2.山西大學(xué) 軟件學(xué)院，太原 030013

1 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）由一系列配備微處理器、微型傳感器和低功率無(wú)線電設(shè)備的低成本設(shè)備組成，它可以實(shí)現(xiàn)數(shù)據(jù)的傳輸和處理[1-2]?；赪SN的節(jié)能路由協(xié)議可以被分類為基于分層和基于聚類的協(xié)議[3]，這些協(xié)議都依賴于被稱作簇頭（Cluster-Head，CH）的特殊節(jié)點(diǎn)。盡管上述協(xié)議有許多優(yōu)點(diǎn)，但它們大多缺乏可擴(kuò)展性。因此，在大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中，實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)呢?fù)載均衡和高可靠性，仍然是一個(gè)挑戰(zhàn)。

在WSN中，一般通過多徑路由方案[4-5]解決上述問題。文獻(xiàn)[6]介紹了幾種基于蟻群優(yōu)化算法（Ant Colony Optimization Algorithm，ACO）[7]的WSN路由協(xié)議。文獻(xiàn)[8]提出一種多宿主路由協(xié)議SDG，通過在WSN中使用多個(gè)接收器來(lái)克服可伸縮性問題，但該方法增加了路由的能量消耗。文獻(xiàn)[9]提出了一種應(yīng)用于多媒體WSN的適應(yīng)性T-ANT路由協(xié)議，稱作AntSensNet。AntSensNet協(xié)議具有三個(gè)階段：信息更新階段、集群設(shè)置階段和穩(wěn)定階段。在前兩個(gè)階段里，簇形成在接收器中發(fā)起，向多媒體傳感器節(jié)點(diǎn)廣播有限數(shù)量的代理，稱為簇螞蟻（CANT），集群的形成通過匯聚點(diǎn)發(fā)起。在接收到CANT消息之后，成為簇頭的每個(gè)多媒體傳感器節(jié)點(diǎn)將CANT消息轉(zhuǎn)發(fā)給另一簇頭節(jié)點(diǎn)候選者，直到形成簇頭和匯聚點(diǎn)骨干網(wǎng)。在穩(wěn)定階段，通過使用不同的代理產(chǎn)生簇頭和匯聚點(diǎn)之間的路徑。代理機(jī)制的使用一定程度上增加了算法的復(fù)雜度。文獻(xiàn)[10]提出一種基于社群檢測(cè)的WSN路由協(xié)議，利用分布式概率選擇簇頭，以增強(qiáng)社群內(nèi)部節(jié)點(diǎn)與簇頭節(jié)點(diǎn)間的連通性，增加網(wǎng)絡(luò)壽命，然而該算法的數(shù)據(jù)吞吐量有待進(jìn)一步提高。文獻(xiàn)[11]提出一種聚類算法和社團(tuán)檢測(cè)算法相結(jié)合的路由協(xié)議，通過社群聚類策略，可以延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的壽命，但聚類算法的使用使得該算法的能量消耗較大。

本文提出了一種基于改進(jìn)蟻群優(yōu)化算法與分布式社區(qū)檢測(cè)的WSN路由協(xié)議，其主要?jiǎng)?chuàng)新點(diǎn)如下：

（1）將改進(jìn)蟻群優(yōu)化啟發(fā)式算法和分布式社群檢測(cè)的標(biāo)簽傳播（Label Spread，LP）算法[12]相結(jié)合，以分布式、平衡和自主的方式建立社群（集群），而不需要事先定義集群的數(shù)量/百分比、簇頭（CH）數(shù)及額外的變量。

（2）為了使協(xié)議能夠在大規(guī)模網(wǎng)絡(luò)中應(yīng)用，在協(xié)議中使用了社群內(nèi)重傳和社群間多徑傳輸方法，最終數(shù)據(jù)傳輸?shù)目煽啃院拓?fù)載均衡性有了顯著提高。

2 協(xié)議說明

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

本文將WSN表述為一個(gè)基本的無(wú)向加權(quán)圖。定義G=(V,E,W)是一個(gè)簡(jiǎn)單的加權(quán)圖。其中，V是一組節(jié)點(diǎn)，用正整數(shù)1到||V 表示，用于表示傳感器和匯聚點(diǎn)。E是由邊構(gòu)成的集合，表示為ei,j，對(duì)于每個(gè)ei,j∈E，可以通過兩個(gè)節(jié)點(diǎn)的剩余能量函數(shù)計(jì)算并估計(jì)它們的傳輸能量開銷wi,j∈W。

本文還定義了一個(gè)部署函數(shù)φ:V??2，用于在?2空間中放置節(jié)點(diǎn)。因此，為了定義給定節(jié)點(diǎn)的鄰居，需要先根據(jù)給定節(jié)點(diǎn)的傳輸能量確定其最大傳輸半徑R。令d(i,j)表示φ(i)和φ(j)之間的歐氏距離，其中i,j∈V,Ni={j∈V|d(i,j)≤R,i≠j}表示通信范圍為 i的節(jié)點(diǎn)的集合。假定所有節(jié)點(diǎn)都具有相同的傳輸功率，且在i∈Nj和 j∈Ni之間存在一個(gè)雙向的信道。

此外，本文提出的算法還使用了網(wǎng)絡(luò)中社群的概念。社群可以表示為一組高度相關(guān)的節(jié)點(diǎn)的k路分支。社群除了被表示為，在本文中還表示為Vs，其中s是匯聚點(diǎn)。

2.2 改進(jìn)的蟻群優(yōu)化算法

傳統(tǒng)的蟻群算法局部搜索尋優(yōu)能力較好，但算法在后期容易出現(xiàn)搜索速度減慢的現(xiàn)象，甚至?xí)磺?。為此，本?jié)提出一種改進(jìn)的蟻群算法，以提高蟻群算法的尋優(yōu)速度，同時(shí)增加WSN的網(wǎng)絡(luò)壽命。

在搜索過程中，信息素會(huì)越來(lái)越少，此時(shí)有必要計(jì)算出信息素的揮發(fā)量。充分利用搜索路徑中消耗的能量和WSN節(jié)點(diǎn)剩余能量，以避免WSN節(jié)點(diǎn)出現(xiàn)過早休眠的現(xiàn)象，影響路徑中的信息傳輸?；诖耍谒阉鬟^程中使用了位置帶的概念，使螞蟻在不同節(jié)點(diǎn)之間的移動(dòng)具有一定的方向性，這么做能夠使螞蟻準(zhǔn)確地尋找移動(dòng)路徑，節(jié)約能量。如圖1所示，如果WSN節(jié)點(diǎn)位于位置帶n處，當(dāng)該節(jié)點(diǎn)有轉(zhuǎn)發(fā)螞蟻的需求時(shí)，其下一跳節(jié)點(diǎn)只能從其本身和位于位置帶n-1處的節(jié)點(diǎn)中選擇。圖1給出了4個(gè)位置帶，其中節(jié)點(diǎn)A位于位置帶n中，A的鄰居節(jié)點(diǎn)分別是B、C、D、E和F，如上所述，只有節(jié)點(diǎn)C、D和E可作為A的下一跳節(jié)點(diǎn)。使用這種方法選擇下一跳節(jié)點(diǎn)能夠避免處在和Sink節(jié)點(diǎn)（匯聚點(diǎn)）方向相反的位置帶n+1中的節(jié)點(diǎn)轉(zhuǎn)發(fā)螞蟻，同時(shí)，螞蟻到達(dá)Sink節(jié)點(diǎn)的過程中所需的跳數(shù)以及消耗的能量也會(huì)減少。

圖1 螞蟻轉(zhuǎn)發(fā)示意圖

另外，基于信息素，本文將抵抗素的概念應(yīng)用到螞蟻轉(zhuǎn)發(fā)中，使用信息素和抵抗素得到螞蟻轉(zhuǎn)發(fā)的啟發(fā)信息。利用WSN中的多個(gè)節(jié)點(diǎn)分擔(dān)信息傳輸過程消耗的能量，以此來(lái)均衡每個(gè)節(jié)點(diǎn)的能量[13]。把信息傳輸時(shí)消耗的能量和WSN節(jié)點(diǎn)剩余能量聯(lián)合起來(lái)作為評(píng)價(jià)構(gòu)造路徑的要素，在計(jì)算最終的信息素時(shí)就會(huì)更加準(zhǔn)確。當(dāng)某一個(gè)路徑存儲(chǔ)的能量較多時(shí)，有可能會(huì)出現(xiàn)該路徑上的能量過度消耗，改進(jìn)措施則可以避免該現(xiàn)象的出現(xiàn)。

圖2所示為改進(jìn)蟻群算法的影響因素關(guān)系，可以看出，在選擇下一個(gè)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)剩余能量是算法考慮的主要因素，并且路徑的信息素值也受節(jié)點(diǎn)剩余能量的影響。改進(jìn)算法在選擇下一個(gè)節(jié)點(diǎn)時(shí)，同樣使用了篩選策略，當(dāng)節(jié)點(diǎn)處在特定區(qū)域或者其能量滿足一定要求時(shí)，才能成為符合條件的節(jié)點(diǎn)。抵抗素概念的引入也會(huì)對(duì)下一個(gè)節(jié)點(diǎn)的集合產(chǎn)生影響。改進(jìn)蟻群算法的主要貢獻(xiàn)是對(duì)下一個(gè)節(jié)點(diǎn)的選擇更加精確，優(yōu)化了算法性能。

2.3 協(xié)議概述

對(duì)于由傳感器節(jié)點(diǎn)和匯聚點(diǎn)組成的傳感器網(wǎng)絡(luò)。本文提出的協(xié)議具有兩個(gè)階段：建立階段和穩(wěn)定階段。建立階段是在協(xié)議操作開始時(shí)僅運(yùn)行一次的階段，而穩(wěn)定階段持續(xù)運(yùn)行直至WSN的功能結(jié)束。

圖2 改進(jìn)蟻群算法的影響因素

在建立階段，協(xié)議的第一步是通過社群檢測(cè)過程識(shí)別傳感器的社群結(jié)構(gòu)，本文所使用的方法是節(jié)點(diǎn)標(biāo)簽傳播算法（Vertex Label Propagation Procedure，VLBP）[14]。VLBP以異步分布式的方式運(yùn)行，僅使用每個(gè)傳感器節(jié)點(diǎn)i∈V的鄰居信息。在VLBP執(zhí)行結(jié)束以后，每個(gè)社群都被一個(gè)作為社群標(biāo)簽的數(shù)值所標(biāo)識(shí)，這一數(shù)值通常由其成員選擇。

一旦形成了社群，協(xié)議的下一步就是建立這些社群與匯聚點(diǎn)的層級(jí)關(guān)系。在這一步中，使用了社群分層傳播算法（Community Hierachy Propagation，CHP），將不同的社群分配到不同的層級(jí)，算法過程在下文中詳細(xì)描述。這些層級(jí)考慮了社群與匯聚點(diǎn)之間的距離。社群在其邊緣收縮到最大值后可以被視作超級(jí)節(jié)點(diǎn)，在這種情況下，社群與匯聚點(diǎn)的距離就是一系列超級(jí)節(jié)點(diǎn)到匯聚點(diǎn)的最短距離。

在CHP中，節(jié)點(diǎn)間通過傳播社區(qū)層次結(jié)構(gòu)消息（Community Hierarchy Message，CHM）以設(shè)置社群的層次結(jié)構(gòu)級(jí)別。傳播過程從匯聚點(diǎn)開始，初始的級(jí)別設(shè)置為0。接下來(lái)，這一消息在網(wǎng)絡(luò)中以泛洪的形式傳播，每當(dāng)遇到一個(gè)新的社群，級(jí)別值加1。在CHP過程結(jié)束時(shí)，網(wǎng)絡(luò)已經(jīng)完成了分級(jí)。在某一社群中的所有傳感器節(jié)點(diǎn)具有相同的社群級(jí)別。分級(jí)可以使每一個(gè)社群很快發(fā)現(xiàn)與相鄰的較低層級(jí)的社群直接相連的節(jié)點(diǎn)，這些節(jié)點(diǎn)被稱作虛擬匯聚點(diǎn)（Virtual Sink，VS）。

建立階段的最終步驟，被稱為社群內(nèi)部構(gòu)建（Intra-Community Setup，ICS）。在ICS中，每個(gè)被識(shí)別為社群內(nèi)虛擬匯聚點(diǎn)的節(jié)點(diǎn)都會(huì)在其社群內(nèi)發(fā)送一個(gè)虛擬通知消息（Virtual Announcement Message，VAM），其目標(biāo)是獲得傳感器節(jié)點(diǎn)的路由表以及與社群的其他VS的開銷。VAM具有每個(gè)節(jié)點(diǎn)d∈VS的識(shí)別編號(hào)(vsID)、VS的社群標(biāo)簽以及當(dāng)前位置到VS的距離(vsDist)。對(duì)于一個(gè)傳感器節(jié)點(diǎn)i，當(dāng)它從一個(gè)鄰居 j處獲得一個(gè)VAM后，會(huì)比較其接收到的VAM與VS節(jié)點(diǎn)的距離與存儲(chǔ)在路由表中的距離RT.DistVSi,j,d。這一距離和下一跳以及目的對(duì){j,vsID:d=vsID}有關(guān)。如果接收到的VAM中的distVS值較小，就會(huì)更新RT.DistVSi,j,d。在更新階段，節(jié)點(diǎn)i創(chuàng)建一個(gè)它所接收到的VAM的副本，在這份副本中會(huì)將distVS的值傳送給它的下一個(gè)鄰居。在VAM傳播過程結(jié)束后，每個(gè)傳感器i都會(huì)根據(jù)路由表中每一個(gè)下一跳終點(diǎn)初始化它的信息素權(quán)重τi,j,d∈RT，其中τi,j,d=1/RT.distVSi,j,d。

協(xié)議的穩(wěn)定階段包括三個(gè)異步執(zhí)行的過程，分別是信息素濃度蒸發(fā)、社群內(nèi)路由（Intra-Community Routing，ICR）和社群間可靠傳輸（Inter-Community Reliable Transmission，ICRB）。信息素濃度蒸發(fā)過程基于一個(gè)預(yù)定義的信息素濃度衰減參數(shù)，對(duì)傳感器的路由表中每個(gè)記錄的信息素濃度進(jìn)行周期性的衰減。

在ICR過程中，協(xié)議依靠分布路徑?jīng)Q策方法向每個(gè)目的地發(fā)送前向信息。在這一過程中，使用代理數(shù)據(jù)消息（Agent-Data Message，ADM）通過動(dòng)態(tài)多徑來(lái)傳遞感興趣的信息到多個(gè)虛擬匯聚點(diǎn)，并更新傳感器的路由表中路徑信息。每個(gè)ADM的副本都包含著源傳感器節(jié)點(diǎn)ID、終點(diǎn)ID(VSid)、當(dāng)前路徑中下一跳的ID以及路徑的累積剩余能量。路徑的累計(jì)剩余能量可以通過對(duì)路徑中每個(gè)傳感器節(jié)點(diǎn)的剩余能量求和得到。在接收到一個(gè)ADM之后，一個(gè)中轉(zhuǎn)傳感器根據(jù)由式（1）給出的概率 p，自主地決定到達(dá)ADM所指示的虛擬匯聚點(diǎn)的路徑的下一跳。

其中，i∈V是一個(gè)到達(dá)局部虛擬匯聚點(diǎn)的路徑中的一個(gè)中轉(zhuǎn)節(jié)點(diǎn)；d∈V；τi,j,d表示節(jié)點(diǎn) j到d的下一跳的信息素濃度。因此，節(jié)點(diǎn)i在重新將ADM傳送給下一跳節(jié)點(diǎn) j之前，會(huì)先更新路徑和累積剩余能量。一旦ADM到達(dá)了終點(diǎn)的虛擬匯聚點(diǎn)，虛擬匯聚點(diǎn)會(huì)將ADM拷貝到輸出緩沖區(qū)，并將它發(fā)送給靠近匯聚點(diǎn)的下一個(gè)社群。之后，虛擬匯聚點(diǎn)會(huì)根據(jù)式（2）計(jì)算路徑質(zhì)量：

其中，w是一個(gè)(v0,d)路徑，也就是一條v0和d之間的路徑；Eˉ(w)是w中節(jié)點(diǎn)的平均剩余能量。最終，一個(gè)虛擬匯聚點(diǎn)在一個(gè)反向通路中傳送反向代理信息（Backward Agent Message，BAM）。如果源節(jié)點(diǎn)在相同的社群中，BAM 就會(huì)被發(fā)送給源節(jié)點(diǎn)，否則，它將會(huì)被發(fā)送給相鄰的低級(jí)社群。BAM 包含的信息有路徑w、中轉(zhuǎn)節(jié)點(diǎn)ID、目的節(jié)點(diǎn) j以及路徑質(zhì)量q。因此，路徑中的每個(gè)節(jié)點(diǎn)(j∈W,i≠j)都可以根據(jù)式（3）來(lái)更新信息素濃度τi,j,d。

式（3）的意義在于強(qiáng)制使用具有最佳關(guān)聯(lián)的剩余能量和路徑長(zhǎng)度的路徑。

穩(wěn)定階段的最后一步是社群間的可靠傳輸。在這一階段，一個(gè)攜帶著可靠數(shù)據(jù)消息RDM的數(shù)據(jù)包被發(fā)送給靠近匯聚點(diǎn)的下一級(jí)社群。這些信息可能包含聚合的或者不聚合的ADM信息。一旦終點(diǎn)正確接收到了ADM，就會(huì)回傳一個(gè)可靠確認(rèn)信息（RAM），如果RDM受到干擾，終點(diǎn)節(jié)點(diǎn)不會(huì)做任何動(dòng)作。經(jīng)過特定的時(shí)間后，虛擬匯聚點(diǎn)會(huì)注意到缺少確認(rèn)信息，并重傳RDM。

2.3.1 節(jié)點(diǎn)標(biāo)簽傳播算法

節(jié)點(diǎn)標(biāo)簽傳播算法（VLBP）旨在通過考慮節(jié)點(diǎn)鄰居的共識(shí)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行標(biāo)記。算法1給出了VLBP算法的偽代碼，每個(gè)傳感器都使用這一算法定義其自身的標(biāo)簽。

算法1節(jié)點(diǎn)標(biāo)簽傳播算法（VLBP）

1.初始化標(biāo)簽集L={1,2,…,|V|}

2.令mylb為L(zhǎng)中任意值

3.令mylt為false

4.執(zhí)行

5. 設(shè)置m為(mylb,mylt)

6. 廣播(m)

7. 重置timer

8. 當(dāng)timer＜tmax時(shí)

9. 如果接收到消息m′，則

10. 將lt和lb設(shè)置為m′中提取的值

11. 如果true==lt，則將lb加入B

12. 否則，將lb加入A

13. 結(jié)束

14. 結(jié)束

15. 如果A?B=?則

16. mylt=true

17. 否則

20. 如果nlb==mylb，則mylt=true

21. mylb=nlb

23. 結(jié)束

24.直到mylt為空

在這一過程的開始階段，每個(gè)節(jié)點(diǎn)v都被隨機(jī)分配了一個(gè)標(biāo)簽。變量mylt始終跟蹤著當(dāng)前節(jié)點(diǎn)標(biāo)簽的狀態(tài)，如果這一標(biāo)簽不是最終標(biāo)簽，則其值為false，如果這一標(biāo)簽是最終標(biāo)簽，那么它的值就為true。之后，節(jié)點(diǎn)v廣播一個(gè)消息m用于通告它的標(biāo)簽和狀態(tài)。接下來(lái)，就會(huì)開始三個(gè)主要階段的循環(huán)，這一過程由變量timer和一個(gè)最值tmax控制。第一階段會(huì)創(chuàng)建一對(duì)標(biāo)簽集合A和B,A中包含了尚未完全確定標(biāo)簽的鄰居，B由已擁有永久標(biāo)簽的v的鄰居組成。這些集合由第8行至第13行的循環(huán)生成。

如果A或者B不是空集，就會(huì)開始第二階段。否則，當(dāng)前v的標(biāo)簽就定義為節(jié)點(diǎn)的最終標(biāo)簽并結(jié)束這一過程。在第二階段中，大多數(shù)A?B中的標(biāo)簽都在Maj中定義。為了描述這一步，定義一個(gè)函數(shù)c:L→?返回一個(gè)標(biāo)簽在給定集合中的重復(fù)次數(shù)。在第三階段中（第17行至第23行），節(jié)點(diǎn)從集合Maj中隨機(jī)選擇了一個(gè)標(biāo)簽，如果這個(gè)集合的A和B中有標(biāo)簽，就只會(huì)考慮B中的標(biāo)簽。之后，集合A被定義為空集，這是因?yàn)楣?jié)點(diǎn)廣播消息只有在它的標(biāo)簽完全確定以后才會(huì)發(fā)出。

2.3.2 社群層次傳播過程

算法2描述了社群層次傳播過程（CHP），定義了某一社群中節(jié)點(diǎn)與匯聚點(diǎn)間的距離。分層級(jí)別由社群分層消息（CHM）確定，這一消息由源ID（srcID）、源社群標(biāo)簽（srcLB）和源社群級(jí)別（srcLV）三部分組成。

算法2社群分層傳播過程（CHP）

1.令i∈V

2.令LBi是執(zhí)行完VLBP過程后節(jié)點(diǎn)vi的標(biāo)簽

3.令LVi是節(jié)點(diǎn)i的分層級(jí)別

4.令LVNi是每個(gè) j∈Ni的分層級(jí)別集合

5.如果i是匯聚點(diǎn)，則

6. LVi=0；生成CHM m:=(i,LBi,LVi)；廣播m

7.否則

8. LVi←∞，根據(jù)應(yīng)用設(shè)置chpTimer

9. 執(zhí)行

10. 如果從任意 j∈Ni接收到了m'，則

11. LVNi[j]=m′.srcLV

12. 如果 m'.srcLB=LBi，則

13. 如果 m'.srcLV＜LVi，則

14. LVi=m'.srcLV

15. 生成CHM m:=(i,LBi,LVi)；廣播m

16. 結(jié)束

17. 否則m'.rcvLV+1＜LVi,則

18. LVi=m'.rcvLV+1

19. 生成CHM m:=(i,LBi,LVi)；廣播m

20. 結(jié)束

21. 結(jié)束

22.直到chpTimer超時(shí)

23.結(jié)束

在算法2執(zhí)行的開始階段，每一個(gè)節(jié)點(diǎn)i∈V都具有一個(gè)由VLBP過程所產(chǎn)生的社群標(biāo)簽LBi，表明這一節(jié)點(diǎn)屬于某一社群。算法2執(zhí)行的結(jié)果是確定每一個(gè)節(jié)點(diǎn)連接到匯聚點(diǎn)的社群分層級(jí)別，也就是所有屬于這一點(diǎn)鄰居(LVNi)的節(jié)點(diǎn)集合的分層級(jí)別。

2.3.3 社群內(nèi)配置過程

算法3展示了社群內(nèi)配置過程（ICS），在這一過程中，每一個(gè)非匯聚節(jié)點(diǎn)都根據(jù)它的鄰居信息決定其是否為自己所屬社群內(nèi)的虛擬匯聚點(diǎn)。節(jié)點(diǎn)i是一個(gè)虛擬匯聚點(diǎn)，如果它具有一個(gè)以上的鄰居 j，并且這一鄰居節(jié)點(diǎn)的社群標(biāo)簽LBj≠LBi,則社群分級(jí)LVj＜LVi。然后，所有的虛擬匯聚點(diǎn)會(huì)在其社群內(nèi)廣播一個(gè)VAM，從而對(duì)其社群內(nèi)的每一個(gè)非虛擬匯聚點(diǎn)的路由表（RT）進(jìn)行初始化。一個(gè)VAM頭包含如下結(jié)構(gòu)：源ID（srcID）、虛擬匯聚點(diǎn)ID（vsID）、虛擬匯聚點(diǎn)社群標(biāo)簽（vsLB）以及當(dāng)前位置到虛擬匯聚點(diǎn)的距離（distVS）。在算法3所示的過程中，第9至30行對(duì)于任意節(jié)點(diǎn)i∈V的路由表RT，配置了一組可用的虛擬匯聚點(diǎn)(dinVSset)及到達(dá)這一節(jié)點(diǎn)的下一跳 j的開銷τi,j,d。虛擬匯聚點(diǎn)的集合是數(shù)據(jù)消息可能到達(dá)的局部終點(diǎn)的集合。

算法3社群內(nèi)配置過程（ICS）

1.令i∈V，i不是匯聚點(diǎn)

2.令LBj是節(jié)點(diǎn) j的標(biāo)簽，?j∈Ni

3.令LBset,i是節(jié)點(diǎn)i觀測(cè)到的節(jié)點(diǎn) j標(biāo)簽的集合，?j∈Ni

4.令LVi是節(jié)點(diǎn)i在經(jīng)過CHP過程后的分層級(jí)別

5.令VSset是節(jié)點(diǎn)i可達(dá)的社群虛擬匯聚點(diǎn)的集合

6.令RT是節(jié)點(diǎn)i的路由表

7. 如果 ?LBj∈LBset,i且 LBj≠LBi,LVj＜LVi

isVS=true；否則，isVS=false

8.如果LVi＜∞則nodeready=true；否則nodeready=false

9.如果nodeready==true，則

10. 如果isVS==true，則

11. 生成VAM m:=(i,i,LBi,0)，廣播m

13. 設(shè)置vsBroadcastTimer

14. 如果isVS==false，則

15. 執(zhí)行

16. 如果從 ?j∈Ni中接收到一個(gè)VAM m'，滿足 m'.vsLB==LBi，則

17. m'.distVS=m'.distVS+1

18. 如果 m′.vsID?VSset，則

19. VSset=VSset?{m′.vsID}

20. RT.distVSi,j,m′.vsID=m'.distVS

21. 廣播m'

22. 如果 m′.vsDist≤RT.distVSi,j,m′.vsID，則

23. RT.distVSi,j,m′.vsID=m'.distVS

24. 廣播m'

25. 結(jié)束

26. 結(jié)束

27. 直到vsBroadcastTimer超時(shí)

29. 結(jié)束

30.結(jié)束

2.3.4 社群內(nèi)路由過程

所有的活動(dòng)節(jié)點(diǎn)都在協(xié)議的穩(wěn)定階段異步地執(zhí)行社群內(nèi)路由過程（ICR）。算法4和算法5對(duì)這一過程進(jìn)行了詳細(xì)的描述，算法4是社群中虛擬匯聚點(diǎn)所執(zhí)行的路由過程，而算法5是普通的傳感器節(jié)點(diǎn)所執(zhí)行的操作。節(jié)點(diǎn)間的交互是通過ADM和BAM兩種消息實(shí)現(xiàn)的。

算法4由虛擬匯聚點(diǎn)執(zhí)行的社群內(nèi)路由過程

1.令i∈V，在配置階段中nodeready=true

2.令LVi是節(jié)點(diǎn)i在CHP過程后的分層級(jí)別

3.令LBj是節(jié)點(diǎn) j的標(biāo)簽，?j∈Ni

4.令LBset,i是節(jié)點(diǎn)i所觀測(cè)到的所有的節(jié)點(diǎn) j的標(biāo)簽集合，?j∈Ni

5.令VSset是節(jié)點(diǎn)i可能到達(dá)的本社群的虛擬匯聚點(diǎn)

6.令RT是節(jié)點(diǎn)i的路由表

8.令ei是節(jié)點(diǎn)i的剩余能量

9.令ew是路徑w的累積剩余能量

10.執(zhí)行

11. 如果從j∈Ni接收到了一個(gè)ADM m'且m'.vsID=i

12. 如果aggregationTimer超時(shí)

13. ?j∈Ni,LBi≠LBj,nextHopOutCommunity=j

14. enqueueOnRelay(Data,nextHopOutCommunity)

17. nextHopInCommunity=stackPop(m'.w),創(chuàng)建BAM，m:=(i,nextHopInCommunity,i,m'.w,q)

18. 否則

19. Data=Aggregate(m'.payload)

20. 結(jié)束

21. 結(jié)束

22.直到節(jié)點(diǎn)操作結(jié)束

算法5由非虛擬匯聚點(diǎn)執(zhí)行的社群內(nèi)路由過程

1.令i∈V，在配置階段中nodeready=true

2.令VSset是節(jié)點(diǎn)i可能到達(dá)的本社群的虛擬匯聚點(diǎn)

3.令RT是節(jié)點(diǎn)i的路由表

5.令ei是節(jié)點(diǎn)i的剩余能量

6.令ew是路徑w的累積剩余能量

7.執(zhí)行

9. 從applicationDataBuffer中提取數(shù)據(jù)Data

10. 根據(jù)應(yīng)用配置qtyOfDuplicates

11. 對(duì)于i從1到qtyOfDuplicates，執(zhí)行

12. 隨機(jī)在VSset中選擇一個(gè)節(jié)點(diǎn)d

14. w={i}

15. ew=ei

16. 生成ADM消息

17. m:=(i,nextHopInCommunity,d,w,ew)

18. 結(jié)束

19. 結(jié)束

21. 如果從 j∈Ni接收到了一個(gè)ADM m'且m'.destID=i，則

23. m'.srcID=i

24. m'.distID=nextHopInCommunity

25. m′.w=m′.w ? {i}

26. m'.ew=m'.ew+ei

27. 單播m'

28. 結(jié)束

29. 如果從 j∈Ni接收到了一個(gè)BAM m'且m'.destID=i，則

32. nextHopInCommunity=stackPop(m'.w)

33. m'.destID=nextHopInCommunity

34. 單播m'

35. 結(jié)束

36. 結(jié)束

37. 結(jié)束

38.直到節(jié)點(diǎn)操作結(jié)束

由于這些消息的目的地不同，它們的結(jié)構(gòu)也各不相同。ADM由源ID（srcID）、目的ID（destID）、虛擬匯聚點(diǎn)ID（vsID）、當(dāng)前路徑隊(duì)列(w)、當(dāng)前路徑剩余能量(ew)以及數(shù)據(jù)有效負(fù)載組成；BAM由源ID（srcID）、目的ID（destID）、虛擬匯聚點(diǎn)ID（vsID）、當(dāng)前路徑隊(duì)列(w)和由虛擬匯聚點(diǎn)計(jì)算得到的最終路徑質(zhì)量(q)構(gòu)成。

普通傳感器節(jié)點(diǎn)在ICR中扮演的角色可以總結(jié)為兩類：向隨機(jī)選擇的虛擬匯聚點(diǎn)發(fā)送新的聚合數(shù)據(jù)（算法5的第5～15行）和將所接收到的ADM和BAM轉(zhuǎn)發(fā)到下一跳的目的地（算法5的第17～34行）。虛擬匯聚點(diǎn)在ICR中所扮演的角色比較復(fù)雜，因?yàn)樘摂M匯聚點(diǎn)每接收到一個(gè)ADM都需要生成一個(gè)BAM。由于每個(gè)BAM都具有路徑質(zhì)量參數(shù)q，虛擬匯聚點(diǎn)必須要考慮ADM中的w和ew參數(shù)來(lái)計(jì)算它。

虛擬匯聚點(diǎn)可以在一定的時(shí)間間隔對(duì)所接收到的數(shù)據(jù)進(jìn)行聚合，這一時(shí)間間隔在應(yīng)用中由aggregationTimer參數(shù)指定。因此，虛擬匯聚點(diǎn)隨機(jī)選擇一個(gè)位于社群外的鄰居發(fā)送數(shù)據(jù)，并通過enqueueOnRelay函數(shù)將其放入隊(duì)列中。

3 性能分析

3.1 仿真模型與假設(shè)

本文假定模型是適用于靜態(tài)傳感器網(wǎng)絡(luò)的，在這一網(wǎng)絡(luò)中，節(jié)點(diǎn)是均勻分布的，但其具體的位置坐標(biāo)未知。此外，所有的節(jié)點(diǎn)都配備了相同的無(wú)線電設(shè)備和傳輸功率，從而形成了節(jié)點(diǎn)網(wǎng)絡(luò)間的對(duì)稱鏈路。

3.2 度量指標(biāo)

本文使用三種度量指標(biāo)來(lái)評(píng)估提出協(xié)議的性能：實(shí)際吞吐量（交付率）、傳輸延遲和能量消耗。

（1）吞吐量

本文定義的吞吐量是指?jìng)鬟f到匯聚點(diǎn)應(yīng)用層的總消息數(shù)量與每個(gè)節(jié)點(diǎn)所產(chǎn)生的原始數(shù)據(jù)消息的總和的比值，吞吐量由式（4）定義：

其中，Mi是由節(jié)點(diǎn)i產(chǎn)生的原始數(shù)據(jù)消息的集合；Ri是匯聚點(diǎn)接收到的節(jié)點(diǎn)i所發(fā)送出的原始數(shù)據(jù)消息的集合。

（2）傳輸延遲

本文將單個(gè)消息的數(shù)據(jù)傳輸延遲定義為消息從源節(jié)點(diǎn)發(fā)送到匯聚點(diǎn)所消耗的時(shí)間。對(duì)于每一個(gè)節(jié)點(diǎn)，將個(gè)體的傳輸延遲視作總體延遲的均值，因此，可以假定總體的傳輸延遲為所有個(gè)體傳輸延遲的均值。

（3）能量消耗

本文使用處于傳輸狀態(tài)（TX）節(jié)點(diǎn)的能量開銷來(lái)衡量能量消耗。本文在估計(jì)單個(gè)節(jié)點(diǎn)的傳輸能量消耗(Etx)時(shí)考慮了文獻(xiàn)[15]所提出的能量模型：

其中，L是所有傳輸?shù)募希籯是距離為d的傳輸?shù)谋忍財(cái)?shù)（在這種情況下，d是給定tx傳輸功率的最大傳輸距離）；Eelec是傳輸一個(gè)比特的能量消耗；eamp是放大器能量開銷。因此可以對(duì)網(wǎng)絡(luò)的總開銷（單位為J/h）進(jìn)行估計(jì)，總開銷為式（6）中所定義的每次傳輸?shù)哪芰康目偤停?/p>

其中，T是網(wǎng)絡(luò)的總操作時(shí)間。

3.3 仿真參數(shù)和場(chǎng)景

為驗(yàn)證算法的有效性，在NS2（Network Simulator Version 2）仿真環(huán)境下對(duì)本文協(xié)議、文獻(xiàn)[10]、文獻(xiàn)[11]提出的協(xié)議進(jìn)行仿真比較。在500 m×500 m的目標(biāo)區(qū)域內(nèi)部署500～3 000個(gè)節(jié)點(diǎn)，其余參數(shù)如表1所示。

表1 仿真參數(shù)

本文根據(jù)每個(gè)節(jié)點(diǎn)的概率λ來(lái)考慮不同的數(shù)據(jù)生成速率，每個(gè)節(jié)點(diǎn)在每秒最多產(chǎn)生一條消息。λ的取值分別為0.01、0.02和0.05，分別表示數(shù)據(jù)生成速率由低到高。在模擬中，數(shù)據(jù)生成周期為500秒，從第1 000秒生成開始，到第1 500秒結(jié)束。在這段時(shí)間之后，仿真持續(xù)進(jìn)行直至網(wǎng)絡(luò)中不存在數(shù)據(jù)消息。

3.4 仿真結(jié)果分析

（1）節(jié)點(diǎn)數(shù)量和吞吐量的關(guān)系

圖3是關(guān)于吞吐量的仿真結(jié)果。從圖中可以看出，在所有場(chǎng)景中，本文協(xié)議都比其余兩種協(xié)議具有更好的性能。三種協(xié)議的吞吐量都隨著節(jié)點(diǎn)數(shù)量的增加和λ值的增加而下降，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量和數(shù)據(jù)生成速率λ的增加，網(wǎng)絡(luò)的沖突情況也顯著增加。由于本文協(xié)議使用了基于主動(dòng)確認(rèn)的社群內(nèi)重傳機(jī)制，它可以提供較強(qiáng)的消息傳輸可靠性。文獻(xiàn)[10]和文獻(xiàn)[11]提出的協(xié)議僅僅是利用社群檢測(cè)技術(shù)增加網(wǎng)絡(luò)的連通性，相比之下，本文協(xié)議能夠取得更好的效果。

（2）節(jié)點(diǎn)數(shù)量和能量消耗的關(guān)系

能量消耗的平衡依然是大規(guī)模WSN中的一個(gè)重要問題。圖4是三種協(xié)議的能量消耗情況。雖然本文協(xié)議能比其余兩種協(xié)議傳送更多的原始數(shù)據(jù)，它的每小時(shí)平均能量消耗卻比其余兩種協(xié)議有所降低。事實(shí)上，本文協(xié)議使用社群方法的主要優(yōu)勢(shì)就是降低代理在距離和能量消耗方面的開銷。因此，實(shí)驗(yàn)結(jié)果表明，使用改進(jìn)蟻群算法在社群內(nèi)更新和維護(hù)路由路徑，可以減少能量消耗。另外，從圖4中還能看出，當(dāng)數(shù)據(jù)生成速率λ越來(lái)越大時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)間傳輸?shù)南⒁苍絹?lái)越多，因此能量消耗也越來(lái)越大。

（3）節(jié)點(diǎn)數(shù)量和傳輸延遲的關(guān)系

圖5為三種協(xié)議的傳輸延遲情況。當(dāng)數(shù)據(jù)生成速率λ一定時(shí)，三種協(xié)議的傳輸延遲都隨著節(jié)點(diǎn)數(shù)量的增加而增大。當(dāng)λ=0.01時(shí)，本文協(xié)議的傳輸延遲和文獻(xiàn)[10]協(xié)議相差不大，均優(yōu)于文獻(xiàn)[11]協(xié)議的傳輸延遲；但隨著λ逐漸增大，網(wǎng)路中需要傳輸?shù)南⒅饾u增加，相應(yīng)的社群內(nèi)重傳機(jī)制執(zhí)行的次數(shù)也會(huì)增加，因此出現(xiàn)本文協(xié)議的傳輸延遲大于其余兩種協(xié)議的傳輸延遲，如圖5（b）、（c）所示。

4 結(jié)束語(yǔ)

圖3 節(jié)點(diǎn)數(shù)量和吞吐量的關(guān)系

圖4 節(jié)點(diǎn)數(shù)量和能量消耗的關(guān)系

圖5 節(jié)點(diǎn)數(shù)量和傳輸延遲的關(guān)系

本文闡釋了在大規(guī)模網(wǎng)絡(luò)中使用群智能協(xié)議的優(yōu)越性，并提出了一種基于改進(jìn)蟻群優(yōu)化算法與分布式社區(qū)檢測(cè)的WSN路由協(xié)議，由仿真結(jié)果可知，本文協(xié)議在吞吐量、能量消耗等方面體現(xiàn)出了一定的優(yōu)勢(shì)。利用改進(jìn)的蟻群優(yōu)化算法和標(biāo)簽傳播技術(shù)來(lái)降低代理的開銷，從而減小網(wǎng)絡(luò)負(fù)載和內(nèi)存開銷。使用一種基于主動(dòng)確認(rèn)的社群內(nèi)重傳機(jī)制，在保證較低的能量開銷的前提下，提供了較強(qiáng)的消息傳輸可靠性。

下一步工作將考慮使用多個(gè)移動(dòng)的匯聚點(diǎn)收集數(shù)據(jù)，以減小傳輸延遲，從而更好地滿足WSN的應(yīng)用需求。