基于遺傳算法的WSN謠傳路由的改進

朱錢祥，孫志毅

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

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

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

1 相關定義

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

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

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

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

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

Et(i，j)是節點i向節點j轉發大小為kbit的數據包所消耗的能量，Er(j)是節點j接收大小為kbit數據包所消耗的能量，d為節點i和節點j之間的距離。

2 算法的設計

2.1 算法思想

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

2.2 算法的步驟

初始的種群的產生

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

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

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

圖1 謠傳路由Fig.1 Rumor routing

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

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

(3)事件agent按上述步驟進行移動直至event(k)_ttl變為0.

(4)同理，匯聚節點發送的查詢agent在網絡中轉移的步驟如事件agent轉移策略一樣。

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

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

遺傳算法對路徑的優化:

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

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

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

圖2 交叉操作Fig.2 Intersect operation

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

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

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

3 仿真設計與結果分析

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

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

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

圖3 GARR和RR產生的路徑Fig.3 Paths generated by GARR and RR

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

4 結束語

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

[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]戴世瑾，張翼德，李樂民.無線傳感器網絡的路由協議研究與分析[J].計算機應用研究，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]郭紹永，談 冉.遺傳算法在無線傳感器網絡中的應用[J].微計算機信息，2009(10):125-127.

[6]吉云，徐玉斌.基于地理位置劃分的無線傳感器網絡分簇算法[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多路徑路由優化[J].計算機應用，2009.29(2):521-524.