唐萬偉

(唐山學院 智能與信息工程學院，河北 唐山 063020)

?

WSN中基于蟻群算法的單向鏈路路由算法

唐萬偉

(唐山學院 智能與信息工程學院，河北 唐山 063020)

提出了一種無線傳感器網絡中基于蟻群算法的單向鏈路路由算法，該算法采用單向鏈路和雙向鏈路相結合的方法，尋找源節(jié)點到目的節(jié)點的最優(yōu)路徑。仿真結果表明，該算法能夠選擇參數(shù)性能好的路徑，最優(yōu)路徑上的總時延遠遠小于只支持雙向鏈路的傳統(tǒng)蟻群算法，而且最優(yōu)路徑的收斂速度明顯加快，由此節(jié)省了無線傳感器網絡中的能耗。

無線傳感器網絡；路由算法；蟻群算法；單向鏈路

0 引言

無線傳感器網絡(Wireless Sensor Network，簡稱WSN)是由大量靜止或移動的傳感器以自組織和多跳的方式構成的無線網絡，它以協(xié)作的方式感知、采集、處理和傳輸網絡覆蓋地理區(qū)域內被感知對象的信息，并最終把這些信息發(fā)送給網絡的所有者。隨著WSN技術不斷的發(fā)展，近年來對WSN的研究也越來越受到人們的關注[1]。在WSN中，由于節(jié)點傳輸能力的不同，以及障礙物的阻擋等問題，會使得通信鏈路中存在大量的單向鏈路。因此有研究者提出了基于單向鏈路的路由算法，采用維護多跳反向路由的方法支持單向鏈路[2]，但這種方法的弊端是數(shù)據包在轉發(fā)中需要攜帶完整的反向路由，加大了網絡資源的消耗。而如何有效降低能耗以延長網絡的生命周期是WSN中最具挑戰(zhàn)性的關鍵問題之一[3-5]。有學者提出了一個應用到強連通支配集中的常數(shù)近似算法，將強連通支配集運用到強連通支配和吸收集中[6]，但是這種算法也增加了額外的開銷。而有效利用極為有限的帶寬資源是WSN設計中另一個關鍵問題。有學者在經典的AODV協(xié)議的基礎上利用協(xié)作中繼技術擴大覆蓋范圍來解決單向鏈路問題[7]，但是該方法用到WSN時會出現(xiàn)因覆蓋范圍擴大造成通信鏈路間的干擾問題。筆者在只支持雙向鏈路蟻群算法[8]的基礎上提出一種無線傳感器網絡中基于蟻群算法的單向鏈路路由算法，該算法采用單向鏈路和雙向鏈路相結合的方法，尋找源節(jié)點到目的節(jié)點的最優(yōu)路徑。

1 路由算法分析

無線傳感器網絡中由于節(jié)點發(fā)射功率差異及干擾等因素會導致網絡中單向鏈路的出現(xiàn)，如圖1所示。目前所提出的路由協(xié)議大多是基于雙向鏈路的，即把單向鏈路屏蔽，而只利用雙向鏈路[9]。這些協(xié)議在某些情況下可能使通信無法正常工作，如圖2所示。

圖1 節(jié)點發(fā)射功率差異引起的單向鏈路

圖2 屏蔽單向鏈路使得通信無法進行的情況

筆者根據傳統(tǒng)的蟻群算法[10]，提出一種適用于WSN中的基于蟻群算法的單向鏈路路由算法，其中螞蟻是網絡中的控制報文，總體上分為前向螞蟻(forward ants，F(xiàn)ants)、后向螞蟻(backward ants，Bants)以及廣播后向螞蟻(broadcast backward ants，Bbants)，路由的選擇是通過螞蟻之間的交互信息來最終確定。該算法的路由建立過程的具體步驟如下：

Ⅰ.打開節(jié)點，使節(jié)點接入網絡，并且每個節(jié)點都需要維護一個信息素表用來記錄到鄰居節(jié)點的轉移概率。

Ⅱ.在源節(jié)點產生、發(fā)送m只Fants，并將源節(jié)點置于禁忌表tabuk中，其中k=1，2，…，m。m為在源節(jié)點發(fā)送的螞蟻數(shù)目。禁忌表tabuk記錄第k個螞蟻走過的路徑。

Ⅲ.根據下面的轉移概率公式(1)選擇下一跳節(jié)點，然后將該節(jié)點置于tabuk表中，重復本步驟直到源節(jié)點發(fā)送的m個Fants都找到目的節(jié)點或者沒有下一跳節(jié)點可走時結束。

(1)

上式中，τij(t)表示t時刻在ij路徑上積累的信息素強度；ηij(t)表示螞蟻從節(jié)點i轉到節(jié)點j的期望程度，allowedk={V-tabuk}表示螞蟻下一步允許選擇的節(jié)點集，V是節(jié)點i的鄰居節(jié)點集；tabuk為禁忌表，表示螞蟻k走過的節(jié)點集；α為信息啟發(fā)式因子，表示軌跡的相對重要性；β為期望啟發(fā)式因子，表示能見度的相對重要性。

Ⅳ.經過t時間后，源節(jié)點發(fā)送的m只Fants都完成了一個循環(huán)，此時判斷每只Fants是否都找到了自己對應的目的節(jié)點，如是就生成一個相應的Bants單播出去。否則產生Bbants，尋找Fants到達節(jié)點前一跳的路徑，到達前一節(jié)點后，依據相應的Fants中的信息更新信息素；中間節(jié)點重復本步驟，直到到達源節(jié)點。

Ⅴ.清空tabuk，跳到步驟Ⅱ，再順序執(zhí)行步驟Ⅲ，Ⅳ，Ⅴ步，直到k次迭代都完成。

該算法中，網絡路由的建立過程即為源節(jié)點到目的節(jié)點的最優(yōu)路徑的尋找過程。

2 仿真與分析

將本文提出的單向鏈路的蟻群算法和只支持雙向鏈路的蟻群算法，在兩種網絡拓撲的情況下做一比較。

第一種情況，在源節(jié)點和目的節(jié)點之間只存在單向鏈路。設計3個節(jié)點的網絡拓撲圖如圖3所示。節(jié)點(x，y，z)代表實際通信中物體的三維坐標。仿真參數(shù)α=1，β=1，迭代次數(shù)K=20，每次迭代中Fants個數(shù)m=10，源節(jié)點S=1，目的節(jié)點D=3。對只支持雙向鏈路的蟻群算法及WSN中單向鏈路的蟻群算法進行仿真。

圖3 只有單向鏈路可到達目的節(jié)點的網絡拓撲圖

仿真結果表明，對于只支持雙向鏈路的蟻群算法，源節(jié)點1始終無法找到目的節(jié)點3的路徑。而運用WSN中單向鏈路的蟻群算法進行仿真時，能夠找到到達目的節(jié)點的路徑1→3，以及1→2→3，并會選擇1→3作為傳輸路徑以節(jié)省網絡資源。

第二種情況，同時存在單向鏈路和雙向鏈路的情況。設含有8個節(jié)點的網絡拓撲圖如圖4所示。圖中由于障礙物的阻擋在節(jié)點0和節(jié)點3之間，以及節(jié)點7和節(jié)點2之間存在單向鏈路。仿真參數(shù)同上。

圖4 單向和雙向鏈路同時存在的網絡拓撲圖

在此網絡中存在8個節(jié)點，且有兩條單向鏈路，設源節(jié)點為S=0，目的節(jié)點D=7分別對只支持雙向鏈路的蟻群算法和WSN中基于蟻群算法的單向鏈路路由算法進行仿真，得出結果只支持雙向鏈路的蟻群算法date1和WSN中基于蟻群算法的單向鏈路路由算法date2如圖5所示。

圖5 網絡拓撲仿真結果

由圖5可以看出，只支持雙向鏈路的蟻群算法到達最優(yōu)路徑的收斂速度明顯低于本文提出的WSN中基于蟻群算法的單向鏈路路由算法，并且當網絡拓撲中存在的單向鏈路上的性能參數(shù)優(yōu)于雙向鏈路時，單向鏈路上的時延是小于雙向鏈路的。

3 結論

本文提出的WSN中基于蟻群算法的單向鏈路路由算法通過使用單向鏈路和雙向鏈路相結合的方式，使最優(yōu)路徑上的總時延遠遠小于僅支持雙向鏈路的傳統(tǒng)蟻群算法的總時延，因此節(jié)省了WSN網絡中的能耗。

[1] 王辛果，張信明，陳國良.時延受限且能量高效的無線傳感網絡跨層路由[J].軟件學報，2011，22(7)：1626-1640.

[2]RamashubramanianV，MosseDBRA.AbidirectionalroutingabstractionforasymmetricmobileAdHocnetworks[J].IEEE/ACMTransactionsonNetworking，2008，16(1)：116-129.

[3] 王小明，盧俊嶺，李英姝，等.模糊隨機環(huán)境下的無線傳感器網絡多約束多路徑路由[J].計算機學報，2011，34(5)：779-791.

[4] 劉權，王曉東.MR2-GRADE：一種基于梯度值的無線傳感器網絡高能效多徑干擾避免路由協(xié)議[J].電子學報，2011，39(3)：147-152.

[5] 郝曉辰，竇晶晶，劉浩然，等.基于鏈路質量的WSN代價均衡路由選擇算法[J].電子與信息學報，2012，5(9)：1212-1218.

[6]ThaiMT，TiwariR，DuDZ.OnconstructionofvirtualbackboneinwirelessAdHocnetworkswithunidirectionallinks[J].IEEETransactionsonMobileComputing，2008，7(9)：1098-1109.[7] Yamada K， Umebayashi K， Kamiya Y， et al. A study on routing protocol suitable for directional links[J]. Radio and Wireless Symposium，2010，21：1596-1597.

[8] 孫艷歌，劉明，許芷巖.Ad Hoc網絡中基于雙向收斂蟻群算法的QoS路由算法[J].微電子學與計算機，2006，23(10)：1-3.

[9] 王換招，梅濤，姬凱，等.基于單向鏈路的低開銷Ad Hoc路由策略[J].北京郵電大學學報，2010，33(2)：111-115.

[10] 胡祥培，丁秋雷，李永先.蟻群算法研究評述[J].管理工程學報，2008，22(2)：74-79.

(責任編校：夏玉玲)

A Unidirectional-Link Routing Algorithm for WSN Based Ant Colony Algorithm

TANG Wan-wei

(College of Intelligence and Information Engineering， Tangshan University， Tangshan 063020， China)

Based ant colony algorithm， the author of this paper proposes a unidirectional-link routing algorithm for wireless sensor network(WSN)， in which one-way links and two-way links are combined to determine the optimal path from the source node to the destination node. The simulation results show that the algorithm is capable of deciding best performance parameters， and that the total delay of the path is far less than that of the traditional ant colony algorithm， which supports only bidirectional links， and that the convergence speed of the path increases significantly， thus reducing the energy consumption in wireless sensor networks.Key Words： wireless sensor network； routing algorithm； ant colony algorithm； unidirectional link

唐萬偉(1984-)，男，遼寧凌源人，講師，碩士，主要從事無線通信技術、信號處理研究。

TP393

A

1672-349X(2016)03-0009-03

10.16160/j.cnki.tsxyxb.2016.06.003