傳感器網絡中基于蟻群優化的謠傳協議

（1.長江大學 計算機科學學院， 湖北 荊州 434023； 2.武漢大學 計算機學院， 武漢 430072）



摘要：

謠傳協議是傳感器網絡中基于數據查詢的路由協議，它使用隨機方式生成路由，形成的數據傳輸路徑不是最優路徑，并且可能存在回路。為此，提出一種基于蟻群優化的謠傳協議。該協議將蟻群分成查詢螞蟻和事件螞蟻兩個種群。當兩個種群的螞蟻相遇時，則形成查詢路徑。該協議解決了謠傳協議中的回路問題，算法收斂性好，建立完整查詢路由的概率比謠傳協議的要大，傳輸數據所需的能量消耗比謠傳協議的要少，是一種能量高效的數據查詢協議。

關鍵詞：無線傳感器網絡; 謠傳路由; 蟻群優化; 數據查詢

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

文章編號：10013695(2009)03103303



Rumor routing based on ant colony optimization for wireless sensor networks



CUI Yanrong1，2， CAO Jiaheng2， HE Ning2， ZHU Fan2



(1.School of Computer Science， Yangtze University， Jingzhou Hubei 434023， China; 2. School of Computer， Wuhan University， Wuhan 430072， China)



Abstract:

Rumor routing is a routing protocol based on query for wireless sensor networks， the data transmission paths establish by rumor routing were random and not optimal and maybe exit loop. So this paper put forward a rumor routing based on ant colony optimization(RRACO)， which had resolved the loop route that established by rumor routing， and had good convergence， comparing with rumor routing. AARCO has more probability of forming a data query path， less energy consumption for data transmission， AARCO is an energyefficient data query protocol.

Key words：wireless sensor network; rumor routing; ant colony optimization; data query



無線傳感器網絡是近幾年發展起來的一種新型網絡，它融合了傳感器技術、微機電系統、現代網絡和無線通信技術[1]，能廣泛應用于軍事、環境監測和預報、健康護理、智能家居等領域[2]，具有廣闊的應用前景。但傳感器網絡節點的計算能力、處理能力、存儲容量和電池能量十分有限，如何高效使用能量來最大化網絡生命周期是傳感器網絡面臨的首要挑戰。目前已有大量的研究工作從不同角度來力求延長傳感器網絡的生命周期[3~6]。本文從能量均衡的角度出發，提出一種基于蟻群優化[7]的謠傳路由協議RRACO（rumor routing based on ant colony optimization）。

1相關工作

謠傳協議[8]適用于數據傳輸量較少或者已知事件區域的傳感器網絡中，它利用事件區域中的傳感器節點產生代理（agent）消息，代理消息沿隨機路徑向外擴散傳播，同時匯聚節點發送的查詢消息也沿隨機路徑在網絡中傳播，當代理消息和查詢消息的傳輸路徑交叉在一起時，就形成一條匯聚節點到事件區域的完整路徑。但該協議形成的路徑中可能包含回路，形成的路徑也不一定最優，還需要維護事件表和收發agent，這樣帶來的開銷會很大。

2基于蟻群優化的謠傳協議

2.1相關定義

定義1 事件。傳感器節點能夠感知并能處理的數據。

定義2 事件中心。產生事件的傳感器節點。

定義3 事件距離。節點距離事件中心的跳數，用hopevent表示。

定義4 查詢距離。節點距離sink節點的跳數，用hopquery表示。

定義5 事件螞蟻。由事件區域的傳感器節點在感知到事件后產生的數據包。數據包中包含產生感知到該事件的節點消息、事件消息、節點離事件中心的跳數、該節點的鄰居節點消息。其中產生事件螞蟻的節點將自己的跳數設為0，即hopevent=0；鄰居節點的消息包括鄰居節點的剩余能量、鄰居節點離事件中心的距離，這里指距離事件中心的跳數。

定義6 查詢螞蟻。由sink節點發出查詢任務后，收到查詢任務的節點產生的數據包。數據包中包含節點的ID，查詢任務，以及節點距離sink節點的跳數，節點的鄰居節點的消息。其中產生查詢螞蟻的節點將自己距離sink節點的跳數設為1，即hopquery=1；鄰居節點的消息包括鄰居節點的剩余能量、鄰居節點離sink節點的距離。

定義7 事件螞蟻路徑。事件螞蟻隨機選擇下一跳鄰居節點，將事件傳播出去的路徑。

定義8 查詢螞蟻路徑。查詢螞蟻隨機選擇下一跳鄰居節點，將查詢任務傳播出去的路徑。

定義9 完整的查詢路徑。當事件螞蟻路徑與查詢螞蟻路徑相交時，則產生一條從事件中心到sink節點的路徑，這條路徑就是完整的查詢路徑。

對節點間的距離分為物理距離和通信距離，定義如下：

定義10物理距離。節點vi和vj之間的實際距離，記為dp。

dp=(xvi-xvj)2+(yvi-yvj)2(1)

定義11 通信距離。節點vi和vj之間的信號的強弱程度，記為dvivj。

dvivj=1/Eresidual×d2p(2)

2.2算法思想

事件區域（圖中的灰色區域）的傳感器節點感知到數據后，產生事件螞蟻，事件螞蟻根據狀態轉移概率在自己的鄰居節點中選擇下一跳節點將事件消息傳播出去，形成事件螞蟻路徑；查詢消息由sink傳播，收到查詢消息的節點產生查詢螞蟻，查詢螞蟻根據狀態轉移概率在自己的鄰居節點中選擇下一跳將查詢任務傳播出去，形成查詢螞蟻路徑，當事件螞蟻遇到查詢螞蟻時，則形成一條完整的從事件中心到sink節點的查詢路徑，如圖1所示。

2.3狀態轉移函數

事件螞蟻和查詢螞蟻在產生后均會選擇下一跳鄰居節點進行事件消息和查詢任務的傳播，謠傳路由是隨機選擇，在選擇下一跳過程中沒有考慮節點的能量，得到的路徑不一定是最優的，另外選擇過程中也可能產生回路。在RRACO算法中用蟻群優化算法來選擇下一跳鄰居節點，同時將鄰居節點的能量考慮進去，得到能量最高的最優路徑，同時利用信息素的揮發，當完整查詢路徑上的能量消耗到一定程度時，加大該條路徑上信息素的揮發，從而讓螞蟻選擇另外的一條路徑作為新的完整查詢路徑，以此來均衡傳感器網絡中能量的消耗。

先來看看事件螞蟻如何選擇自己的下一跳鄰居節點。

事件螞蟻k（k=1，2，…，m，且m＜n）（m是事件螞蟻數量）在運動過程中，根據各條路徑上的信息素決定其轉移方向，這里用鄰居節點的當前剩余能量和通信距離相結合構成邊上的信息素，用禁忌表tabuk(k=1，2，…，m)記錄螞蟻k當前所走過的節點，則螞蟻k在t時刻由節點vi選擇節點vj做下一跳鄰居節點的狀態轉移概率為

pkvivj(t)=[τvivj(t)]α×[ηvivj(t)]β/∑vjabuk[τvivj(t)]α×[ηvivj(t)] β，if vjtabuk0，if vj∈tabuk(3)

其中：τvivj(t)表示t時刻路徑(vi，vj)上的信息素，網絡初始時，各路徑上的信息素相等，即τvivj(0)=const。ηvivj(t)為啟發函數，將鄰居節點的剩余能量Evj_residual和距離dvivj相結合作為事件螞蟻選擇下一跳的啟發函數，見式(4)。

ηvivj(t)=Evj_residual/dvivj（4）

α、β分別是信息啟發式因子和期望啟發式因子，是兩個參數，信息啟發式因子反映了螞蟻在運動過程中所積累的信息在螞蟻選擇下一跳所起的作用，其值越大，則該螞蟻傾向于選擇其他螞蟻經過的路徑，螞蟻之間協作性越強。

期望啟發式因子反映了節點剩余能量和節點間距離對螞蟻選擇下一跳的影響，其值越大，則該狀態轉移概率越接近于貪心規則。

在每只事件螞蟻遇到查詢螞蟻或是遇到sink節點時，通過式（5）對路徑上的信息素進行調整，即t+n時刻在路徑（vi，vj）上的信息素可以表示為

τvivj(t+n)=(1-ρ)×τvivj(t)+Δτvivj(t)（5）

Δτvivj(t)=∑mk=1Δτkvivj(t)（6）

Δτkvivj(t)=Q/Lk，第k只螞蟻經過（vi，vj）0，否則（7）

其中：ρ表示信息素揮發系數，1-ρ表示信息素殘留因子，為了防止信息的無限累積，本文讓0≤ρ≤1；Δτvivj(t)表示本次循環中路徑(vi，vj)上的信息素增量，初始時刻Δτvivj(0)=0，Δτkvivj(t)表示第k只螞蟻在本次循環中留在路徑(vi，vj)上的信息量；Q表示信息素強；Lk表示第k只螞蟻在本次循環中所走路徑的總長度，總長度是事件螞蟻遇到查詢螞蟻時離事件中心的跳數。

查詢螞蟻用同樣的轉換概率選擇自己的下一跳，不同之處在于每只查詢螞蟻遇到事件螞蟻或是遇到源節點時，通過式（5）對路徑上的信息素進行調整。

2.4算法步驟

2.4.1事件螞蟻移動步驟

事件螞蟻移動步驟如下：

a）網絡初始時，所有節點的hopevent和hopquery均為NULL。

事件中心根據一定的閾值產生事件螞蟻k，事件螞蟻k知道自己鄰居節點的消息，同時生成一張禁忌表tabuk，事件中心節點將自己距離事件中心的跳數設為0，即hopevent=0，同時加入到tabuk；

b）事件螞蟻計算到鄰居節點的通信距離，根據鄰居節點的剩余能量，利用式（3）選擇自己的下一跳鄰居節點：

（a）若下一跳鄰居節點的hopevent=NULL，則選擇該鄰居節點作為自己的下一跳，并將下一跳鄰居節點距離事件中心的跳數加1，即hopevent=hopevent+1；

（b）若下一跳鄰居節點的hopevent不為空，即該節點已經在tabuk中，狀態轉換概率為0，則從該節點以外的其他鄰居節點中選擇自己的下一跳；

（c）若該節點的所有鄰居節點均在tabuk中，而還沒遇到查詢螞蟻，則事件螞蟻回退一步，再去選擇下一跳節點。

c）若事件螞蟻遇到查詢螞蟻或是遇到sink節點，則形成完整查詢路徑；否則轉b）。

d）利用式（5）更新所經過邊的信息素。

2.4.2查詢螞蟻移動步驟

查詢螞蟻移動步驟如下：

a）Sink節點發出查詢消息后，收到查詢消息的鄰居節點產生查詢螞蟻s，并將自己的hopquery設置為1，同時生成一張禁忌表tabus，將自己加入到表中。

b）查詢螞蟻計算到鄰居節點的通信距離，根據鄰居節點的剩余能量，利用式（3）選擇自己的下一跳鄰居節點：

（a）若下一跳鄰居節點的hopquery=NULL，則選擇該鄰居節點作為自己的下一跳，并將下一跳鄰居節點距離sink節點的跳數加1，即hopquery=hopquery+1；

（b）若下一跳鄰居節點的hopquery不為空，即該節點已經在tabus中，則狀態轉換概率為0，那么就從該節點以外的其他鄰居節點中選擇自己的下一跳；

（c）若該節點的所有鄰居節點均在tabus中，而還沒遇到事件螞蟻或事件中心，則查詢螞蟻回退一步，然后再去選擇下一跳節點。

c）若遇到事件螞蟻或是遇到事件中心節點，則形成完整查詢路徑；否則轉b）。

d）利用式（5）更新所經過邊的信息素。

3算法仿真與結果分析

將rumor routing和RRACO從成功形成查詢路由的概率和協議在查詢過程中傳輸數據數量兩方面進行了比較。Rumor routing中的agent與RRACO中的事件螞蟻數量相等，查詢數量與查詢螞蟻相等，RRACO中的參數如下：Q=100，α=1，β=5，ρ=0.5。

100個節點分布在100 m×100 m的矩形區域，5個sink節點均勻分布在矩形區域外，所有節點靜止不動。

圖2是兩種協議下建立完整查詢路由的概率，由圖2可知rumor routing分發60%查詢消息的概率接近100%，而能100%建立完整查詢路由的概率是0，RRACO協議如果不能終止于事件螞蟻與查詢螞蟻的相遇，則一定會中止sink節點或源節點，所以任何時候均可以建立一條完整的查詢路由。

圖3是當網絡中的事件螞蟻取值為30時（此時rumor routing的性能比較好），查詢螞蟻分別取10、20、30、40時不同協議下網絡中的數據傳輸量，可見RRACO協議比謠傳協議傳輸的數據量要少約50%。

4結束語

謠傳協議是一種比較典型的基于數據查詢的協議，但謠傳協議在形成的路徑中可能包含回路；另外，謠傳協議隨機選擇下一跳，得到的路徑也不一定是最優的，該協議需要維護事件表和收發agent，帶來較大的能量開銷。為此本文提出了基于蟻群優化的謠傳協議，該協議通過事件螞蟻與查詢螞蟻的相向相遇形成完整查詢路由，若事件螞蟻與查詢螞蟻不能相遇，則算法分別中止sink節點或源節點，即RRACO協議可以形成完整的查詢路由，算法具有很好的收斂性。事件螞蟻和查詢螞蟻在移動中，均選擇通信距離小并且當前剩余能量大的鄰居節點作為自己的下一跳，并且利用禁忌表和回退機制避免生成環路，形成的完整查詢路由是能量高效的查詢路由。

參考文獻：

[1]AKYILDIZ IF， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: a survey[J]. Elsevier Sci B V Comp Networks， 2002， 38(4):393422.

[2]ESTRIN D， GOVINDAN R， HEIDEMANN J， et al. Next century challenges: scalable coordination in sensor networks[C]//KODESH H. Proc of ACM/IEEE MobiCom’99. New York: ACM Press，1999:263270.

[3]崔艷榮，曹加恒，何寧，等. 能量高效的傳感器網絡數據查詢路由[J].計算機應用研究， 2008， 25（2）:562564.

[4]YE Wei， HEIDENMANN J， ESTRIN D. An energry efficient MAC protocol for wireless sensor networks[C]//Proc of IEEE INFOCOM. New York: IEEE， 2002:15671576.

[5]KULIK J， HEINZELMAN W R， BALAKRISHNAN H. Negotiation based protocols for dissemination information in wireless sensor networks[J]. ACM Wireless Networks， 2002， 8(2):169185.

[6]HEINZELMAN W R， KULIK J， BALAKRISHNAN H. Adaptive protocols for information dissemination in wireless sensor networks[C]//Proc of the 5th Ann International Conference on Mobile Computing and Networking. 2001:174185.

[7] DORIGO M， DICARO G， GAMBARDELLA L M. Ant algorithms for discrete optimization[J]. Artifical Life，1999， 5(2):137172.

[8]BRAGINSKY D， ESTRIN D. Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications. Atlanta:ACM Press，2002:2231.