馬亞軍，王宏亮，國林勇

（遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，撫順113001）

·微機(jī)網(wǎng)絡(luò)與通信·

基于擁塞的改進(jìn)遺傳算法WSNs拓?fù)淇刂?

馬亞軍，王宏亮，國林勇

（遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，撫順113001）

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

WSNs網(wǎng)絡(luò)；MST結(jié)構(gòu)；擁塞；拓?fù)淇刂?；遺傳算法；優(yōu)化仿真

1 引言

拓?fù)淇刂萍夹g(shù)是無線傳感器網(wǎng)絡(luò)中最重要的技術(shù)之一。在由無線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓?fù)渲写嬖诖罅康倪?，從而?dǎo)致網(wǎng)絡(luò)拓?fù)湫畔⒘看?、路由?jì)算復(fù)雜，浪費(fèi)了寶貴的計(jì)算資源。因此，需要研究無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂茊栴}，在維持拓?fù)涞哪承┤中再|(zhì)如連通性、稀疏性、平面性、結(jié)點(diǎn)度數(shù)有界等的前提下，減少拓?fù)渲械倪厰?shù)并避免邊的交叉和通信環(huán)路的形成。

目前對(duì)拓?fù)淇刂频难芯靠梢苑譃閮纱箢悾河?jì)算幾何方法和概率分析方法[1]。其中，層次路由算法作為計(jì)算幾何方法的一種，構(gòu)建MST拓?fù)浔ＷC了網(wǎng)絡(luò)的連通性，并有效規(guī)避了通信邊的交叉問題，成為WSNs研究的一個(gè)熱點(diǎn)，并取得了一定的進(jìn)展[2]。文獻(xiàn)[3-5]就是在節(jié)點(diǎn)布置完成以后，通過拓?fù)淇刂茷閰R聚節(jié)點(diǎn)（Sink）與目的節(jié)點(diǎn)之間的所有節(jié)點(diǎn)設(shè)置單調(diào)遞增的層次號(hào)，從而把整個(gè)網(wǎng)絡(luò)從源節(jié)點(diǎn)（第1層）開始分成了多個(gè)層次，并最終建立了一個(gè)分層路由樹，在此分層路由樹的基礎(chǔ)上解決網(wǎng)絡(luò)擁塞和能耗優(yōu)化問題。

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

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

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

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

基于T-MAC協(xié)議做如下問題假定：WSNs所有節(jié)點(diǎn)隨機(jī)映射在二維平面上，節(jié)點(diǎn)位置固定；所有無線傳感器節(jié)點(diǎn)通信半徑相同。依據(jù)WSNs通信原理，由Sink節(jié)點(diǎn)發(fā)起網(wǎng)絡(luò)廣播通過拓?fù)淇刂菩纬煞謱勇酚蓸洹?/p>

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

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

2.2 WSNs廣播模型

在節(jié)點(diǎn)隨機(jī)布置完成以后，通過拓?fù)淇刂朴蒘ink節(jié)點(diǎn)開始廣播消息，見圖2。

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

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

3 網(wǎng)絡(luò)拓?fù)鋼砣麊栴}分析及拓?fù)淇刂埔罁?jù)

3.1 網(wǎng)絡(luò)拓?fù)鋼砣麊栴}分析

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

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

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

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

3.2 拓?fù)淇刂苾?yōu)化依據(jù)分析

網(wǎng)絡(luò)拓?fù)浣Y(jié)合擁塞抑制的優(yōu)化，即在初始廣播建立的MST基礎(chǔ)上在不改變層次關(guān)系前提下基于擁塞度權(quán)值利用智能算法進(jìn)一步實(shí)施優(yōu)化，實(shí)現(xiàn)擁塞均衡控制基礎(chǔ)上的MST分層路由樹重構(gòu)。問題的實(shí)現(xiàn)上表現(xiàn)為結(jié)合廣播優(yōu)化分層路由樹求解網(wǎng)絡(luò)拓?fù)涞囊該砣葹闄?quán)值的最小生成樹問題。

拓?fù)淇刂扑惴ǖ哪繕?biāo)是通過控制結(jié)點(diǎn)的傳輸范圍使生成的網(wǎng)絡(luò)拓?fù)錆M足一定的性質(zhì)，以延長網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)干擾，提高吞吐率[7]。

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

1.連通性。為了實(shí)現(xiàn)結(jié)點(diǎn)間的互相通信，生成的拓?fù)浔仨毐ＷC連通性，即從任何一個(gè)結(jié)點(diǎn)都可以發(fā)送消息到另外一個(gè)結(jié)點(diǎn)。連通性是任何拓?fù)淇刂扑惴ǘ急仨毐ＷC的一個(gè)性質(zhì)。

2.稀疏性。指生成的拓?fù)渲械倪厰?shù)為o(n)，其中n是結(jié)點(diǎn)個(gè)數(shù)。減少拓?fù)渲械倪厰?shù)可以有效減少網(wǎng)絡(luò)中的干擾，提高網(wǎng)絡(luò)的吞吐率，稀疏性還可以簡化路由計(jì)算。

3.平面性。指生成的拓?fù)渲袥]有兩條邊相交。由圖論可知，滿足平面性一定滿足稀疏性。

4.結(jié)點(diǎn)度數(shù)有界。指在生成的拓?fù)渲薪Y(jié)點(diǎn)的鄰居個(gè)數(shù)小于一個(gè)常數(shù)d。降低結(jié)點(diǎn)的度數(shù)可以減少結(jié)點(diǎn)轉(zhuǎn)發(fā)消息的數(shù)量和路由計(jì)算的復(fù)雜度。

4 基于擁塞利用改進(jìn)遺傳算法實(shí)施網(wǎng)絡(luò)拓?fù)淇刂?/h2>

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

4.1 遺傳算法適應(yīng)度函數(shù)設(shè)計(jì)

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

4.2 遺傳編碼數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

WSNs網(wǎng)絡(luò)拓?fù)浔硎霾捎绵徑颖砻枋觯妶D3。此種數(shù)據(jù)結(jié)構(gòu)便于劃分網(wǎng)絡(luò)拓?fù)渖蓸渥訕湟约氨闅v記錄節(jié)點(diǎn)總負(fù)荷值（t+1），并于每代進(jìn)化完成后給節(jié)點(diǎn)屬性t賦值。

遺傳基因表述則采用鄰接矩陣描述，見圖4。便于解決平面性問題，即生成的拓?fù)渲胁荒苡袃蓷l邊相交，分層路由思想很好地解決了這個(gè)問題，繼而將約束進(jìn)化過程中相同level值節(jié)點(diǎn)間的邊舍去。

圖3 WSN網(wǎng)絡(luò)的拓?fù)浼肮?jié)點(diǎn)間的關(guān)系的鄰接表描述

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

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

4.3 遺傳進(jìn)化效率改進(jìn)

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

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

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

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

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

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

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

類型1破圈方法：

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

圖6 類型1破圈

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

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

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

類型2破圈方法：

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

圖8 類型2破圈

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

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

圖9 類型2破圈

類型3破圈方法：

圖10 類型3破圈

假設(shè)圖中sink為層次最低的節(jié)點(diǎn)，x和y同為它的兩個(gè)不同Level層次的子節(jié)點(diǎn)，與此同時(shí)x和y又同為父子關(guān)系?？梢缘弥獂節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的跳數(shù)至少為1，y節(jié)點(diǎn)與sink節(jié)點(diǎn)的跳數(shù)至少為2。在與sink節(jié)點(diǎn)的連接中，y節(jié)點(diǎn)通過x節(jié)點(diǎn)建立的連接與y節(jié)點(diǎn)直接建立的連接相比,y節(jié)點(diǎn)通過x節(jié)點(diǎn)建立的連接層次更深且跳數(shù)更多。在實(shí)際情況中因?yàn)樘鴶?shù)過多，容易造成數(shù)據(jù)丟失的情況，且加大了x節(jié)點(diǎn)傳感器的能源消耗，所以我們?cè)谠撉闆r下應(yīng)該選擇破跳數(shù)最多，且層次最深的一條邊。

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

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

5 系統(tǒng)仿真

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

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

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

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

6 結(jié)束語

仿真結(jié)果驗(yàn)證了基于擁塞的WSNs拓?fù)淇刂蒲芯康目尚行?，以及改進(jìn)遺傳算法解決方案的有效性，達(dá)到了WSNs數(shù)據(jù)匯集一定程度的優(yōu)化效果。

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

[1]樓俐,范建華,徐誠.基于局部穩(wěn)定性測度的戰(zhàn)術(shù)移動(dòng)自組織網(wǎng)絡(luò)拓?fù)鋬?yōu)化抗干擾技術(shù)研究 [J].兵工學(xué)報(bào),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]陳文廣,牛玉剛,鄒媛媛.基于改進(jìn)AODV路由協(xié)議的WSNs擁塞控制和能耗均衡策略[J].計(jì)算機(jī)工程與科學(xué),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)絡(luò)數(shù)據(jù)匯集樹生成算法[J].自動(dòng)化學(xué)報(bào),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)絡(luò)MAC協(xié)議能量有效性的研究與MATLAB的仿真[J].沈陽航空工業(yè)學(xué)院學(xué)報(bào),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]陳柯君,王宏亮,李東生.利用遺傳算法實(shí)現(xiàn)基于多目標(biāo)約束的網(wǎng)絡(luò)規(guī)劃[J].微處理機(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

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

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

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