朱利民，趙 麗

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

2.山西大學 軟件學院，太原 030013

1 引言

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

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

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

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

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

2 協(xié)議說明

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

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

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

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

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

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

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

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

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

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

2.3 協(xié)議概述

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

圖2 改進蟻群算法的影響因素

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

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

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

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

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

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

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

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

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

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

2.3.1 節(jié)點標簽傳播算法

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

算法1節(jié)點標簽傳播算法（VLBP）

1.初始化標簽集L={1,2,…,|V|}

2.令mylb為L中任意值

3.令mylt為false

4.執(zhí)行

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

6. 廣播(m)

7. 重置timer

8. 當timer＜tmax時

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為空

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

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

2.3.2 社群層次傳播過程

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

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

1.令i∈V

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

3.令LVi是節(jié)點i的分層級別

4.令LVNi是每個 j∈Ni的分層級別集合

5.如果i是匯聚點，則

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超時

23.結(jié)束

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

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

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

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

1.令i∈V，i不是匯聚點

2.令LBj是節(jié)點 j的標簽，?j∈Ni

3.令LBset,i是節(jié)點i觀測到的節(jié)點 j標簽的集合，?j∈Ni

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

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

6.令RT是節(jié)點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中接收到一個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超時

29. 結(jié)束

30.結(jié)束

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

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

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

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

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

3.令LBj是節(jié)點 j的標簽，?j∈Ni

4.令LBset,i是節(jié)點i所觀測到的所有的節(jié)點 j的標簽集合，?j∈Ni

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

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

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

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

10.執(zhí)行

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

12. 如果aggregationTimer超時

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é)點操作結(jié)束

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

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

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

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

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

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

7.執(zhí)行

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

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

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

12. 隨機在VSset中選擇一個節(jié)點d

14. w={i}

15. ew=ei

16. 生成ADM消息

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

18. 結(jié)束

19. 結(jié)束

21. 如果從 j∈Ni接收到了一個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接收到了一個BAM m'且m'.destID=i，則

32. nextHopInCommunity=stackPop(m'.w)

33. m'.destID=nextHopInCommunity

34. 單播m'

35. 結(jié)束

36. 結(jié)束

37. 結(jié)束

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

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

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

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

3 性能分析

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

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

3.2 度量指標

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

（1）吞吐量

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

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

（2）傳輸延遲

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

（3）能量消耗

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

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

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

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

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

表1 仿真參數(shù)

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

3.4 仿真結(jié)果分析

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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