朱錢祥，孫志毅

(太原科技大學電子信息工程學院，太原030024)

無線傳感器網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)，現(xiàn)已廣泛的應(yīng)用于工業(yè)、農(nóng)業(yè)和軍事等方面。它布置大量而廉價的傳感器節(jié)點到要監(jiān)測的區(qū)域[1]，通過多跳的方式將監(jiān)測到的信息傳送到匯聚節(jié)點。由于傳感器節(jié)點的工作環(huán)境的限制，它本身帶有的電源是不可替換，因此節(jié)點的能量是有限的，如何高效的使用能量延長網(wǎng)絡(luò)的壽命就成了無線傳感器網(wǎng)絡(luò)路由設(shè)計主要面對的問題[2]。

謠傳路由[3]是Braginsky等人提出的適用于數(shù)據(jù)傳輸量較少的傳感器網(wǎng)絡(luò)的一種路由協(xié)議，它通過事件消息和查詢消息隨機產(chǎn)生的路徑交叉生成源節(jié)點到匯聚節(jié)點的路徑。該算法雖然克服了洪泛方式[4]建立轉(zhuǎn)發(fā)路徑所帶來的“內(nèi)暴”等問題，但卻存在路徑非最優(yōu)化的問題，本文從能量消耗最優(yōu)的角度出發(fā)，提出了一種基于遺傳優(yōu)化[5]的路由算法GARR(Rumor Routing based on Genetic Algorithm)。

1 相關(guān)定義

定義1 事件agent:從事件區(qū)域中心的節(jié)點(源節(jié)點)出發(fā)在網(wǎng)絡(luò)中隨機傳播并產(chǎn)生一個事件路徑，它包含有:發(fā)生事件的信息，距離源節(jié)點的跳數(shù)event_hop，生命周期event_ttl，所處節(jié)點的編號event_id，已產(chǎn)生的路徑能量消耗量event_elec，以及產(chǎn)生一個禁忌表event_tabu(用來包含已經(jīng)過的節(jié)點的編號)。

定義2 節(jié)點:無線傳感器網(wǎng)絡(luò)構(gòu)成的基本元素，在本文中，各個節(jié)點都知道其坐標以及通信范圍，并能根據(jù)節(jié)點之間的距離自發(fā)的調(diào)整其發(fā)射功率。它包含節(jié)點本身的初始能量node_elec，節(jié)點的編號node_id.各節(jié)點的鄰居節(jié)點表node_neighbor(節(jié)點的通信范圍內(nèi)的所有節(jié)點編號)以及該節(jié)點到各個鄰居節(jié)點的所需能量消耗值。

定義3 查詢agent:從匯聚節(jié)點出發(fā)在網(wǎng)絡(luò)中隨機傳播產(chǎn)生一個查詢路徑。它包含查詢事件的信息，距離匯聚節(jié)點的跳數(shù)queer_hop，生命周期queer_ttl，所處節(jié)點的編號queer_id，已產(chǎn)生的路徑能量消耗量queer_elec，以及產(chǎn)生一個禁忌表queer_tabu(用來包含已經(jīng)過的節(jié)點的編號)。

定義4 完整的路徑:當事件路徑和查詢路徑產(chǎn)生交點時，通過這個交點連結(jié)兩條路徑行成一個從源節(jié)點到匯聚節(jié)點的完整的路由。

定義5 節(jié)點間的能量消耗:節(jié)點i和節(jié)點j間的能量消耗[6]:

Et(i，j)是節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)大小為kbit的數(shù)據(jù)包所消耗的能量，Er(j)是節(jié)點j接收大小為kbit數(shù)據(jù)包所消耗的能量，d為節(jié)點i和節(jié)點j之間的距離。

2 算法的設(shè)計

2.1 算法思想

如圖1所示:當事件區(qū)域有事件發(fā)生時，其中心的節(jié)點產(chǎn)生事件agent，并在網(wǎng)絡(luò)中心隨機傳播，同時匯聚節(jié)點產(chǎn)生查詢agent，也隨機產(chǎn)生一條路徑，并和事件路徑交叉行成一條新的路由。由于這兩個agent是隨機傳播的，因此該路徑可能產(chǎn)生回路并且非最優(yōu)的，浪費了大量不必要的開銷。由于遺傳算法[7]不依賴于事件的連續(xù)性、可導(dǎo)性，只依賴于其評價函數(shù)的性質(zhì)，對初始種群進行一代代的優(yōu)化直至找到最優(yōu)值，因此，利于遺傳算法對多條從源節(jié)點到匯聚節(jié)點的路徑組成的種群進行優(yōu)化，通過交叉、變異操作[8]，產(chǎn)生最優(yōu)的個體，也即最優(yōu)的路由路徑。

2.2 算法的步驟

初始的種群的產(chǎn)生

(1)當事件區(qū)域有事件發(fā)生，節(jié)點A產(chǎn)生50個事件agent，event(k)_hop為0，event_tabu包含有源節(jié)點A，每個agent移向下一跳節(jié)點，這個過程滿足:

a.下一節(jié)點必須在事件agent所處節(jié)點i的鄰居節(jié)點表node(i)_neighbor內(nèi)。

b.下一節(jié)點必須不包含于該agent的禁忌表中(防止出現(xiàn)回路)。

圖1 謠傳路由Fig.1 Rumor routing

c.若是下一跳節(jié)點為孤立節(jié)點(也即該節(jié)點的通信范圍內(nèi)只有上一跳節(jié)點沒有其它節(jié)點)，則執(zhí)行回退策略，即返回到上一跳節(jié)點重新選擇節(jié)點進行轉(zhuǎn)移。

(2)當事件agent從節(jié)點i轉(zhuǎn)移到節(jié)點j時，event(k)_hop 加 1，event(k)_ttl減 1，將節(jié)點i的編號添加到event(k)_tabu中，將所需的能耗cost(i，j)加到event(k)_elec中。

(3)事件agent按上述步驟進行移動直至event(k)_ttl變?yōu)?.

(4)同理，匯聚節(jié)點發(fā)送的查詢agent在網(wǎng)絡(luò)中轉(zhuǎn)移的步驟如事件agent轉(zhuǎn)移策略一樣。

(5)事件agent和查詢agent所產(chǎn)生的兩條鏈路幾個交點中，隨機選擇一個交點進行兩條路徑的連結(jié)，形成一個新的鏈路，對此鏈路進行回路的消除，產(chǎn)生一個新的從源節(jié)點到匯聚節(jié)點的路徑though(k)。

(6)按照上述步驟產(chǎn)生50條路徑作為初始的種群P，然后利用遺傳算法對該種群進行優(yōu)化。

遺傳算法對路徑的優(yōu)化:

(7)對種群P中第k條路徑進行適應(yīng)值的計算，采用的適應(yīng)值函數(shù)為:

(8)在種群P中選擇最優(yōu)的10條路徑保存下來(取適應(yīng)值最大的10條)，然后按輪盤法選擇38條路徑進行交叉操作產(chǎn)生38個新的個體，最后隨機選擇2條路徑進行變異操作，這樣就構(gòu)成新的下一代的種群P.

交叉操作分為單點交叉和雙點交叉兩種，本文采用單點交叉，具體做法是:判斷兩條路徑是否有相同的節(jié)點，若有一個或超過一個的相同點，隨機選擇一個相同點進行單點交叉，若沒有相同點，則保持不變，交叉操作如圖2所示。

圖2 交叉操作Fig.2 Intersect operation

a是路徑though(i)所經(jīng)過所有節(jié)點的編號，b是路徑though(j)所經(jīng)過所有節(jié)點的編號，a和b中相同的節(jié)點有3和5(除掉源節(jié)點1和匯聚節(jié)點100)，隨機選擇一個節(jié)點作為交叉節(jié)點，在此，選擇節(jié)點5作為交叉節(jié)點，產(chǎn)生了新的路徑a1和b11.在路徑a1中，存在著回路 3、5、6、8，消除該回路便產(chǎn)生了新了路徑a11，將b11和a11作為新的個體保存到下一代種群中去。

變異操作:在路徑i中隨機選擇一個節(jié)點作為變異節(jié)點，重新建立該節(jié)點到匯聚節(jié)點的路徑代替原路徑節(jié)點i后的節(jié)點編號。

(9)通過上述操作，由上一代的最優(yōu)10個路徑，交叉生成的38條路徑，變異生成的2條路徑組合成新一代的種群P，然后對此種群再進行選擇、交叉、變異操作，直至適應(yīng)值趨向于穩(wěn)定時，此時適應(yīng)值最大的路徑為最優(yōu)路徑。

3 仿真設(shè)計與結(jié)果分析

使用MATLAB進行仿真，在200 m×200 m范圍內(nèi)放置100個節(jié)點，各個節(jié)點都是隨機布置的，所有的節(jié)點一旦放置好了便不能移動，假設(shè)源節(jié)點坐標為(0，0)，匯聚節(jié)點的坐標為(200，200)，每個節(jié)點的初始能量都一樣，εelec=5.0×10-9J/bit·m2，Eelec=5.0 ×10-9J/bit，數(shù)據(jù)包大小為4 000 bit.

圖3是謠傳路由算法和GARR算法所形成的兩條路徑。由仿真結(jié)果可知，謠傳路由算法產(chǎn)生的路徑傳送一個數(shù)據(jù)包消耗的能量為10.383 5 J，而由GARR算法產(chǎn)生的路徑傳送一個數(shù)據(jù)包則消耗2.111 7 J，節(jié)約了近 78.7%的能量。

圖4是種群代數(shù)和各代種群中最優(yōu)個體(也即最優(yōu)路徑)傳送一個數(shù)據(jù)包所消耗的能量之間的關(guān)系，由圖可知，當運算到第34代時，得出的最優(yōu)路徑的就接近于最終的結(jié)果，由此可以看出，GRAA算法運算較少次便可計算出結(jié)果，運算所消耗的能量相比于通信消耗的能量可以忽略不記。

圖3 GARR和RR產(chǎn)生的路徑Fig.3 Paths generated by GARR and RR

圖4 不同優(yōu)路徑消耗能量值Fig.4 The energy consumption of different paths

4 結(jié)束語

謠傳路由是典型的基于數(shù)據(jù)查詢的無線傳感器路由，它克服了洪泛方式建立轉(zhuǎn)發(fā)路徑帶來的開銷過大的問題，但是由于其事件消息和查詢消息的隨機擴散，便產(chǎn)生了路徑非最優(yōu)的問題。本文提出的GARR算法采用了在事件消息和查詢消息中加入了禁忌表的方式、采用遺傳優(yōu)化的思想計算出最優(yōu)路徑，減少了節(jié)點能量的使用，極大的延長的網(wǎng)絡(luò)的使用壽命。

[1]ALYILDIV I F，SU W，SANKARASUBRAMANIAM Y，CAYIRCI E.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2]戴世瑾，張翼德，李樂民.無線傳感器網(wǎng)絡(luò)的路由協(xié)議研究與分析[J].計算機應(yīng)用研究，2006，23(12):294-297.

[3]BRAGINSKY D，ESTRIN D.Rumor routing algorithm for sensor networks[C]∥Proceeding of the 1st Workshop on Sensor Networks and Application.Atlanta:ACM Press，2002:22-31.

[4]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al.Directed Diffusion for Wireless Sensor Networking[J].IEEE/ACM Transactions on Networking，2003，11(1):2-16.

[5]郭紹永，談 冉.遺傳算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用[J].微計算機信息，2009(10):125-127.

[6]吉云，徐玉斌.基于地理位置劃分的無線傳感器網(wǎng)絡(luò)分簇算法[J].太原科技大學學報，2010，31(1):6-9.

[7]GOLDBERG D E.Genetic algorithms in search，optimization，and machine learning[M].New York:Addison Wesley，1989.

[8]周集良，李彩霞，曹奇英.基于遺傳算法的WSNs多路徑路由優(yōu)化[J].計算機應(yīng)用，2009.29(2):521-524.