馬亞軍，王宏亮，國林勇

（遼寧石油化工大學計算機與通信工程學院，撫順113001）

·微機網(wǎng)絡與通信·

基于擁塞的改進遺傳算法WSNs拓撲控制*

馬亞軍，王宏亮，國林勇

（遼寧石油化工大學計算機與通信工程學院，撫順113001）

WSNs分層路由樹是計算幾何方法拓撲控制的一種，結合真實約束條件在廣播構建的最小生成樹（MST）基礎上優(yōu)化分層路由樹，有利于提高網(wǎng)絡吞吐量、降低網(wǎng)絡干擾、節(jié)約結點資源。從網(wǎng)絡負荷均衡思想出發(fā)，研究了降低網(wǎng)絡結構帶來的擁塞幾率問題。提出基于擁塞重構分層路由樹的方法，并結合網(wǎng)絡拓撲控制需滿足的連通性、稀疏性、平面性和結點度數(shù)有界性改進遺傳算法實現(xiàn)分層路由樹重構的優(yōu)化仿真，驗證了研究的有效性。

WSNs網(wǎng)絡；MST結構；擁塞；拓撲控制；遺傳算法；優(yōu)化仿真

1 引言

拓撲控制技術是無線傳感器網(wǎng)絡中最重要的技術之一。在由無線傳感器網(wǎng)絡生成的網(wǎng)絡拓撲中存在大量的邊，從而導致網(wǎng)絡拓撲信息量大、路由計算復雜，浪費了寶貴的計算資源。因此，需要研究無線傳感器網(wǎng)絡中的拓撲控制問題，在維持拓撲的某些全局性質如連通性、稀疏性、平面性、結點度數(shù)有界等的前提下，減少拓撲中的邊數(shù)并避免邊的交叉和通信環(huán)路的形成。

目前對拓撲控制的研究可以分為兩大類：計算幾何方法和概率分析方法[1]。其中，層次路由算法作為計算幾何方法的一種，構建MST拓撲保證了網(wǎng)絡的連通性，并有效規(guī)避了通信邊的交叉問題，成為WSNs研究的一個熱點，并取得了一定的進展[2]。文獻[3-5]就是在節(jié)點布置完成以后，通過拓撲控制為匯聚節(jié)點（Sink）與目的節(jié)點之間的所有節(jié)點設置單調遞增的層次號，從而把整個網(wǎng)絡從源節(jié)點（第1層）開始分成了多個層次，并最終建立了一個分層路由樹，在此分層路由樹的基礎上解決網(wǎng)絡擁塞和能耗優(yōu)化問題。

但是MST拓撲過于理想化，以結點間歐式距離為度量的最小生成樹僅僅保證了網(wǎng)絡的連通性、平面性以及距離的優(yōu)化，為了得到更符合實際的量化結果，則需要使用更真實的模型。以負荷均衡為例，MST在網(wǎng)絡拓撲結構上就無法兼顧結構本身對應用的支持，從而無法有效抑制擁塞問題的發(fā)生。因此，需引進約束條件進一步優(yōu)化MST構建的符合應用實際的分層路由樹?；谶z傳算法的改進就是其中一個方向。

2 WSNs網(wǎng)絡模型與廣播模型

2.1 WSNs網(wǎng)絡模型假定

假設WSNs網(wǎng)絡為層次型結構，由多個簇組成，每一個簇都由一個簇頭節(jié)點和若干普通節(jié)點構成。簇頭節(jié)點形成一個處理并轉發(fā)數(shù)據(jù)的骨干網(wǎng)，將數(shù)據(jù)融合結果通過多跳路由發(fā)送給基站（Sink），如圖1。

基于T-MAC協(xié)議做如下問題假定：WSNs所有節(jié)點隨機映射在二維平面上，節(jié)點位置固定；所有無線傳感器節(jié)點通信半徑相同。依據(jù)WSNs通信原理，由Sink節(jié)點發(fā)起網(wǎng)絡廣播通過拓撲控制形成分層路由樹。

圖1 WSNS網(wǎng)絡模式

規(guī)定 WSNs每個節(jié)點具有 id，parent，level，energy，t等多個屬性。Sink節(jié)點的parent為盡可能大的一個規(guī)模值（如9000）；t為以本節(jié)點為根的子樹的節(jié)點個數(shù)；level和t的初值為0。在節(jié)點布置完成后，由Sink節(jié)點發(fā)出廣播信息。各節(jié)點energy值初始定義均為電池滿電量E；其它節(jié)點隨著距離Sink節(jié)點的遠近具有不同的level值（增量加1），具體的level值通過網(wǎng)絡廣播獲得；parent值在網(wǎng)絡廣播時與level同時獲得。記錄消息“單跳”傳播的父節(jié)點，即信息接收節(jié)點的parent值為信息發(fā)送節(jié)點的id，t則記錄本節(jié)點id作為parent值的所有子樹中節(jié)點的總個數(shù)，表現(xiàn)為節(jié)點負荷，在廣播結束后賦值。

2.2 WSNs廣播模型

在節(jié)點隨機布置完成以后，通過拓撲控制由Sink節(jié)點開始廣播消息，見圖2。

圖2 網(wǎng)絡廣播模型

接收到廣播消息的節(jié)點將發(fā)送節(jié)點的level值加1作為自己的level值，同時，記錄發(fā)送節(jié)點的id作為本節(jié)點的parent值。當節(jié)點再次收到不同的發(fā)送節(jié)點傳來的消息時，如果新節(jié)點的level值小于原來發(fā)送節(jié)點的level值，則替換掉原來發(fā)送節(jié)點的數(shù)據(jù)，使用新的發(fā)送節(jié)點的level及parent，反之，將新的發(fā)送節(jié)點的消息拋棄。

3 網(wǎng)絡拓撲擁塞問題分析及拓撲控制依據(jù)

3.1 網(wǎng)絡拓撲擁塞問題分析

對于一棵數(shù)據(jù)匯集樹,假設其深度為N，給定層次 i，i＜N。從i+1到N的所有節(jié)點，若總共有M個節(jié)點,則這M個節(jié)點產生的數(shù)據(jù)流必然全部通過第i層。假設節(jié)點x 為根的子樹中的節(jié)點個數(shù)為 tx，第i層上有n個節(jié)點，其t值分別為且最大時，之間的差值最小，負荷最均衡，擁塞問題產生的幾率最小。

其中，ti表j示第i層節(jié)點的t值。

根據(jù)公式（1）的擁塞度權值定義，網(wǎng)絡擁塞度權值的最小生成樹定義為：

由此網(wǎng)絡中的每棵子樹都能計算出各自的擁塞度權值，繼而求得全網(wǎng)絡的擁塞度權值

3.2 拓撲控制優(yōu)化依據(jù)分析

網(wǎng)絡拓撲結合擁塞抑制的優(yōu)化，即在初始廣播建立的MST基礎上在不改變層次關系前提下基于擁塞度權值利用智能算法進一步實施優(yōu)化，實現(xiàn)擁塞均衡控制基礎上的MST分層路由樹重構。問題的實現(xiàn)上表現(xiàn)為結合廣播優(yōu)化分層路由樹求解網(wǎng)絡拓撲的以擁塞度為權值的最小生成樹問題。

拓撲控制算法的目標是通過控制結點的傳輸范圍使生成的網(wǎng)絡拓撲滿足一定的性質，以延長網(wǎng)絡生命周期，降低網(wǎng)絡干擾，提高吞吐率[7]。

這里我們考查以下幾個性質，作為優(yōu)化的依據(jù)：

1.連通性。為了實現(xiàn)結點間的互相通信，生成的拓撲必須保證連通性，即從任何一個結點都可以發(fā)送消息到另外一個結點。連通性是任何拓撲控制算法都必須保證的一個性質。

2.稀疏性。指生成的拓撲中的邊數(shù)為o(n)，其中n是結點個數(shù)。減少拓撲中的邊數(shù)可以有效減少網(wǎng)絡中的干擾，提高網(wǎng)絡的吞吐率，稀疏性還可以簡化路由計算。

3.平面性。指生成的拓撲中沒有兩條邊相交。由圖論可知，滿足平面性一定滿足稀疏性。

4.結點度數(shù)有界。指在生成的拓撲中結點的鄰居個數(shù)小于一個常數(shù)d。降低結點的度數(shù)可以減少結點轉發(fā)消息的數(shù)量和路由計算的復雜度。

4 基于擁塞利用改進遺傳算法實施網(wǎng)絡拓撲控制

遺傳算法利用簡單的編碼技術和繁殖機制來表現(xiàn)復雜的對象，從而解決非常困難的問題（如全局最優(yōu)化問題）。它不受搜索空間的限制性假設約束，不必要求諸如連續(xù)性、可導性、單峰性等假設，以及其固有的并行性，遺傳算法目前已經在最優(yōu)化、機器學習和并行計算等領域取得了越來越廣泛的應用[8]。

4.1 遺傳算法適應度函數(shù)設計

依據(jù)前文對網(wǎng)絡擁塞問題的分析，取網(wǎng)絡擁塞度權值為進化判據(jù)：

4.2 遺傳編碼數(shù)據(jù)結構設計

WSNs網(wǎng)絡拓撲表述采用鄰接表描述，見圖3。此種數(shù)據(jù)結構便于劃分網(wǎng)絡拓撲生成樹子樹以及遍歷記錄節(jié)點總負荷值（t+1），并于每代進化完成后給節(jié)點屬性t賦值。

遺傳基因表述則采用鄰接矩陣描述，見圖4。便于解決平面性問題，即生成的拓撲中不能有兩條邊相交，分層路由思想很好地解決了這個問題，繼而將約束進化過程中相同level值節(jié)點間的邊舍去。

圖3 WSN網(wǎng)絡的拓撲及節(jié)點間的關系的鄰接表描述

圖4 以鄰接矩陣表示基因示意圖

結點度數(shù)有界控制：設定節(jié)點度數(shù)上界（假定為每個節(jié)點可以同時與3個以下的節(jié)點通信），同時建立節(jié)點負荷伴隨矩陣，記錄優(yōu)化過程中生成樹的各個節(jié)點直接負荷，節(jié)點度數(shù)上界結合負荷伴隨矩陣作為遺傳進化約束條件[9]。

4.3 遺傳進化效率改進

4.3.1 遺傳算法問題域空間的收縮

廣播形成的MST作為初始種群的基因之一，其他基因在MST層次特性約束下隨機產生，WSNs拓撲布局要求網(wǎng)絡節(jié)點全連通，且滿足稀疏性和平面性。依據(jù)圖論思想，由圖論可知n個節(jié)點網(wǎng)絡全連通至少擁有n+1條邊，故對于少于n+1條邊的生成網(wǎng)絡直接舍棄；依據(jù)分層路由思想，相同level值的節(jié)點間邊舍去；對符合上述條件的基因從Sink節(jié)點進行深度優(yōu)先全連通檢測。

4.3.2 交叉、變異過程中環(huán)路問題破圈改進

針對不同類型的環(huán)路，有以下三種不同的破圖方法：

（1）環(huán)路類型1及破圈方法

在Level層次大于3的前提下，某一節(jié)點同時收到上一層次Level中的兩個節(jié)點的數(shù)據(jù)傳輸，而這兩個節(jié)點又同時擁有同一個父節(jié)點，則形成了至少橫跨三層Level類似于“菱形”的環(huán)路。環(huán)路類型如圖5所示。

圖5 環(huán)路類型1

類型1破圈方法：

在level（0）層，z節(jié)點作為x,y節(jié)點的共同子節(jié)點，圖中出現(xiàn)環(huán)路，每條邊上的權值代表著此路徑的能量消耗值。如果在不考慮能量消耗的前提下，可以刪掉x,y到z節(jié)點之間的任意一條邊。但在實際情況下，能量消耗是必須要考慮的條件之一。根據(jù)能耗最小的原則，應該刪掉能耗較大的傳輸線路，即圖中權值較大的邊。綜述應刪掉y節(jié)點到z節(jié)點之間的邊。破圈后如圖6所示。

圖6 類型1破圈

（2）環(huán)路類型2及破圈方法

同樣在Level層次大于3的前提下，在通過廣播確定層次后，選取某一個節(jié)點，它與同一層次的另一節(jié)點建立了數(shù)據(jù)傳輸關系，而兩個節(jié)點的父節(jié)點同時擁有同一父節(jié)點，形成了至少橫跨三層Level類似于“五邊形”的環(huán)路。環(huán)路類型2如圖7所示。

圖7 環(huán)路類型2

類型2破圈方法：

在通過跳數(shù)得到各節(jié)點的層次后，分析發(fā)現(xiàn)處在同一Level層次的倆個節(jié)點之間建立了數(shù)據(jù)流連接。而在實際應用中，這種同層次的連接會造成網(wǎng)絡數(shù)據(jù)的重復收集，進而造成了能源浪費。在遵從能耗最小的原則下，為了使無線路由擁有更長久的使用壽命，應當采取適當措施。相比于第一類環(huán)路類型，該類型處理方法比較簡單，只需要刪除同一層次中兩個節(jié)點間的連接，即可打破環(huán)路。破圈后如圖8所示。

圖8 類型2破圈

（3）環(huán)路類型3及破圈方法

同樣在Level層次大于3的前提下，在通過廣播確定層次后，選取某一個節(jié)點。此節(jié)點擁有兩個不同Level層次的父節(jié)點，而兩個父節(jié)點之間又為父子關系，進而形成了一種類似于“三角形”的環(huán)路。環(huán)路類型3如圖9所示。

圖9 類型2破圈

類型3破圈方法：

圖10 類型3破圈

假設圖中sink為層次最低的節(jié)點，x和y同為它的兩個不同Level層次的子節(jié)點，與此同時x和y又同為父子關系。可以得知x節(jié)點與sink節(jié)點之間的跳數(shù)至少為1，y節(jié)點與sink節(jié)點的跳數(shù)至少為2。在與sink節(jié)點的連接中，y節(jié)點通過x節(jié)點建立的連接與y節(jié)點直接建立的連接相比,y節(jié)點通過x節(jié)點建立的連接層次更深且跳數(shù)更多。在實際情況中因為跳數(shù)過多，容易造成數(shù)據(jù)丟失的情況，且加大了x節(jié)點傳感器的能源消耗，所以我們在該情況下應該選擇破跳數(shù)最多，且層次最深的一條邊。

在此種情況下，遵從路徑最短、能耗最小的條件，應當破除跳數(shù)最多且層次最深的一條邊，即破除x節(jié)點與y節(jié)點間的網(wǎng)絡數(shù)據(jù)連接。破圈后如圖10所示。

根據(jù)上述3個基本破圈方法，可在最大化保證網(wǎng)絡數(shù)據(jù)匯集樹能耗最小、路徑最短、數(shù)據(jù)傳輸最高效化的前提下，合理的去邊破除環(huán)路。

5 系統(tǒng)仿真

改進的遺傳算法設計按照MVC架構開發(fā)，采用多線程、多目標并行優(yōu)化策略，即網(wǎng)絡擁塞度和路由優(yōu)化過程在廣播數(shù)據(jù)的基礎上并行進行，仿真測試采用35節(jié)點網(wǎng)絡隨機布局，結點度數(shù)上界設為3。模擬節(jié)點布置完成，遺傳種群基因規(guī)模設定為20，交叉因子取0.6，變異因子取0.05，進化代數(shù)為從50代至250進行了測試，優(yōu)化結果以繪圖和數(shù)值的形式顯示在主窗口上，見圖11，圖中紅色的路徑為最優(yōu)數(shù)據(jù)傳輸路徑。

圖11 遺傳算法優(yōu)化仿真

仿真實驗結果見表1，結果顯示網(wǎng)絡擁塞度（為便于考查擁塞與負荷均衡關系，設計輸出為擁塞度而非擁塞度權值）隨著進化代數(shù)遞增而優(yōu)化（越大，負荷越均衡），表明網(wǎng)絡各節(jié)點的負荷越均衡擁塞概率越小，擁塞問題得到很好解決，全網(wǎng)能量消耗從4E降低到2E，同時保證了數(shù)據(jù)匯集能耗的優(yōu)化。

表1 部分仿真測試數(shù)據(jù)結果

6 結束語

仿真結果驗證了基于擁塞的WSNs拓撲控制研究的可行性，以及改進遺傳算法解決方案的有效性，達到了WSNs數(shù)據(jù)匯集一定程度的優(yōu)化效果。

但是受限于所采用數(shù)學模型的局限性，以及遺傳算法收斂早熟的處置還不夠完善，算法效率仍有待于進一步的研究提高，以期獲更接近于最優(yōu)解的實際應用驗證。

[1]樓俐,范建華,徐誠.基于局部穩(wěn)定性測度的戰(zhàn)術移動自組織網(wǎng)絡拓撲優(yōu)化抗干擾技術研究 [J].兵工學報,2016,37(9):1662-1669.Lou Li,Fan Jianhua,Xu Cheng.Research of Anti-interference Technology Based on the Measure for Local Stability of Tactical Mobile Self-organizing Network Topology Optimization[J].Acta Armamentarii 2016,37(9):1662-166

[2]Andrew S.Tanenbaum.Computer Networks,5th Edition[M].Pearson,2010,10.

[3]Sergiou C,Vassiliou V,Paphitis A.Hierarchical tree alternative path(HTAP)Algorithm for congestion control in wireless sensor networks[J].Ad Hoc Networks,2013,11(1):257-272.

[4]Sergiou C,Vassiliou V,Paphitis A.Congestion control in wirelesssensor networks through dynamic alternative path selection[J].Computer Networks,2014,75(A):226-238.

[5]陳文廣,牛玉剛,鄒媛媛.基于改進AODV路由協(xié)議的WSNs擁塞控制和能耗均衡策略[J].計算機工程與科學,2016,38(9):1776-1783.Chen Wenguan,Niu Yugang,Zou Yuanyuan.WSNs Congestion Control and Energy Consumption Balancing Strategy Based on Improved AODV Routing Protocol[J].Computer Engineering and Science,2016,38(9):1776-1783.

[6]石為人,唐云建,王燕霞.基于擁塞控制的無線傳感器網(wǎng)絡數(shù)據(jù)匯集樹生成算法[J].自動化學報,2010,36(6):823-828.Shi Weiren,Tang Yunjian,Wang Yanxia.Wireless Sensor Network Data Collection Tree Generation Algorithm Based on Congestion Control[J].Acta Automatica Sinical,2010,36(6):823-828.

[7]樊慶亮,武衛(wèi)東,王光興.傳感器網(wǎng)絡MAC協(xié)議能量有效性的研究與MATLAB的仿真[J].沈陽航空工業(yè)學院學報,2006,23(2).Fan Qingliang,Wu Weidong,Wang Guangxing.Study on Energy Effectiveness of Sensor Network MAC Protocol and Simulation of MATLAB[J].Journal of Shenyang Institute of Aeronautical Engineering,2006,23(2).

[8]David E.Goldberg.Genetic Algorithms in Search,Optimization,and Machine Learning[M].Addison-Wesley Professional,1989,1.

[9]陳柯君,王宏亮,李東生.利用遺傳算法實現(xiàn)基于多目標約束的網(wǎng)絡規(guī)劃[J].微處理機,2015,36(2):24-28.Chen Kejun,Wang Hongliang,Li Dongsheng.Using Genetic Algorithm for Network Planning Based on Multi-objective Restriction[J].Microprocessors,2015,36(2):24-28.

Improved Genetic Algorithm WSNs Topology Control Based on Congestion

Ma Yajun，Wang Hongliang，Guo Linyong
(School of Computer and Communication Enginering,Liaoning Shihua University,Fushun 113001,China)

WSNs hierarchical routing tree is a kind of topological control of geometric methods,optimizing hierarchical routing tree based on the minimum spanning tree (MST)of broadcast construction combining real constraints is helpful to improve network throughput,reduces network interference,and saves nodes resources.This paper studies the problem that reducing the congestion probability caused by network structure,and proposes a method of rebuilding hierarchical routing tree based on congestion.Then the optimal simulation is realized by combining the connectivity,sparseness,flatness and node degree of network topology control to improve the genetic algorithm,and the validity of the research is verified.

WSNs;MST;Congestion;Topological control;Genetic algorithm;Optimization simulation

10.3969/j.issn.1002-2279.2017.05.010

TP311.52

A

1002-2279-（2017）05-0035-05

遼寧省教育廳資助科研項目（L2014153）；遼寧省教育科學“十二五”規(guī)劃項目（JG14DB229）

馬亞軍（1995—），男，江蘇省如皋市人，本科生，主研方向：軟件工程。

王宏亮（1971—），男，遼寧省撫順市人，副教授，主研方向：計算機集成制造，軟件工程。