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

唐萬偉

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

?

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

唐萬偉

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

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

無線傳感器網(wǎng)絡(luò)；路由算法；蟻群算法；單向鏈路

0 引言

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

1 路由算法分析

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

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

圖2 屏蔽單向鏈路使得通信無法進(jìn)行的情況

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

Ⅰ.打開節(jié)點(diǎn)，使節(jié)點(diǎn)接入網(wǎng)絡(luò)，并且每個(gè)節(jié)點(diǎn)都需要維護(hù)一個(gè)信息素表用來記錄到鄰居節(jié)點(diǎn)的轉(zhuǎn)移概率。

Ⅱ.在源節(jié)點(diǎn)產(chǎn)生、發(fā)送m只Fants，并將源節(jié)點(diǎn)置于禁忌表tabuk中，其中k=1，2，…，m。m為在源節(jié)點(diǎn)發(fā)送的螞蟻數(shù)目。禁忌表tabuk記錄第k個(gè)螞蟻?zhàn)哌^的路徑。

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

(1)

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

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

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

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

2 仿真與分析

將本文提出的單向鏈路的蟻群算法和只支持雙向鏈路的蟻群算法，在兩種網(wǎng)絡(luò)拓?fù)涞那闆r下做一比較。

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

圖3 只有單向鏈路可到達(dá)目的節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D

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

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

圖4 單向和雙向鏈路同時(shí)存在的網(wǎng)絡(luò)拓?fù)鋱D

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

圖5 網(wǎng)絡(luò)拓?fù)浞抡娼Y(jié)果

由圖5可以看出，只支持雙向鏈路的蟻群算法到達(dá)最優(yōu)路徑的收斂速度明顯低于本文提出的WSN中基于蟻群算法的單向鏈路路由算法，并且當(dāng)網(wǎng)絡(luò)拓?fù)渲写嬖诘膯蜗蜴溌飞系男阅軈?shù)優(yōu)于雙向鏈路時(shí)，單向鏈路上的時(shí)延是小于雙向鏈路的。

3 結(jié)論

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

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

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

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

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

[5] 郝曉辰，竇晶晶，劉浩然，等.基于鏈路質(zhì)量的WSN代價(jià)均衡路由選擇算法[J].電子與信息學(xué)報(bào)，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網(wǎng)絡(luò)中基于雙向收斂蟻群算法的QoS路由算法[J].微電子學(xué)與計(jì)算機(jī)，2006，23(10)：1-3.

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

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

(責(zé)任編校：夏玉玲)

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-)，男，遼寧凌源人，講師，碩士，主要從事無線通信技術(shù)、信號處理研究。

TP393

A

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

10.16160/j.cnki.tsxyxb.2016.06.003