基于三鏈混合遺傳算法的WSNs中Sink節(jié)點布局優(yōu)化

劉燕

（嘉應(yīng)學(xué)院電子信息工程學(xué)院，廣東 梅州 514015）

基于三鏈混合遺傳算法的WSNs中Sink節(jié)點布局優(yōu)化

劉燕

（嘉應(yīng)學(xué)院電子信息工程學(xué)院，廣東 梅州 514015）

對無線傳感器網(wǎng)絡(luò)的設(shè)計和布局中，多Sink節(jié)點的布局是其拓撲設(shè)計的關(guān)鍵，對網(wǎng)絡(luò)通信的能量控制至關(guān)重要。本文通過分析其Sink節(jié)點布局模型，提出一種改進的三鏈混合遺傳算法對Sink節(jié)點布局求取最優(yōu)解。實驗表明，三鏈混合遺傳算法在針對Sink節(jié)點的布局算法中相對于枚舉算法，具有較優(yōu)解，并且算法效率高，可降低無線傳感器網(wǎng)絡(luò)的能耗，改善網(wǎng)絡(luò)性能。

無線傳感器網(wǎng)絡(luò)；Sink節(jié)點布局；三鏈混合遺傳算法

1 引言

無線傳感器網(wǎng)絡(luò)系統(tǒng)是一種由大量部署在監(jiān)控區(qū)域的智能傳感器節(jié)點構(gòu)成的網(wǎng)絡(luò)應(yīng)用系統(tǒng)，一般包含三類不同節(jié)點：傳感器節(jié)點、匯節(jié)點(稱Sink,也稱為基站Base station)和管理節(jié)點[1]。傳感器節(jié)點一般采用隨機投放方式，Sink節(jié)點的布局問題是拓撲控制中的一個難點[2-4]。如何通過功率控制以及骨干節(jié)點的選擇，刪除節(jié)點間不必要的無線通信鏈路，使得網(wǎng)絡(luò)拓撲滿足一定的性質(zhì)，如連通性、稀疏性等，從而減少無線信號沖突，降低無線傳輸能耗，延長網(wǎng)絡(luò)生存時間。因此，對Sink節(jié)點的布局研究具有一定的現(xiàn)實意義[5]。

遺傳算法（Genetic Algorithm，GA）是模擬達爾文“優(yōu)勝劣汰、適者生存”的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法[6]。經(jīng)過國內(nèi)外多年的研究與實踐，遺傳算法已經(jīng)顯示出了其解決復(fù)雜系統(tǒng)優(yōu)化問題的良好能力，對NP組合優(yōu)化問題的求解，更表現(xiàn)出了優(yōu)異的性能。本文中多Sink節(jié)點的P中值布局模型就屬于一類NP完全問題：搜索到Sink節(jié)點的最佳位置，使加權(quán)距離和最小。

2 問題描述

Sink節(jié)點的布局與無線傳感器網(wǎng)絡(luò)的服務(wù)性能緊密相關(guān)?？梢哉J為無線傳感器網(wǎng)絡(luò)中的Sink節(jié)點與傳感器節(jié)點之間存在服務(wù)與被服務(wù)的關(guān)系。由于無線通信鏈路可靠性及服務(wù)效率與服務(wù)點與被服務(wù)點之間的距離有關(guān)，因此縮短Sink節(jié)點與傳感器節(jié)點之間的距離是一種提高服務(wù)效率的有效策略。

于是，對于一個具體的無線傳感器網(wǎng)絡(luò)環(huán)境作如下定義：

表1 問題變量定義表

則問題為在給定區(qū)域內(nèi)，從M個候選Sink節(jié)點位置中找出P個Sink節(jié)點的位置，使得所有傳感器節(jié)點到Sink節(jié)點之間的總加權(quán)距離最小化。加權(quán)值為節(jié)點i單位時間發(fā)送的請求數(shù)ri。

其中總數(shù)學(xué)表達式中的兩個決策變量Kj，Tij的含義如公式（1）所示：

Tij=傳感器節(jié)點i被匯節(jié)點j服務(wù)其他 （1）

同時，此問題還需要滿足以下條件，如表2所示：

表2 問題滿足的條件

3 遺傳算法實現(xiàn)

Sink節(jié)點候選位置可以采用網(wǎng)格方法，將區(qū)域用網(wǎng)格劃分，Sink節(jié)點布局在網(wǎng)格的交叉點上。針對不同的布局要求，網(wǎng)格的密度可以適應(yīng)性改變。

3.1 染色體編碼

根據(jù)上一節(jié)數(shù)學(xué)模型，由于取Sink節(jié)點采取布局在網(wǎng)格交叉點上，因此可以采用Sink節(jié)點的二維坐標(biāo)作染色體，采用二進制編碼。染色體由三條分鏈順序拼接組成，分鏈1表示Sink節(jié)點的x坐標(biāo)；分鏈2表示Sink節(jié)點的y坐標(biāo)，分鏈三表示Sink節(jié)點單位時間所能處理的請求數(shù)目。

3.2 適應(yīng)值函數(shù)和選擇操作

針對上一節(jié)提出的數(shù)學(xué)模型，目標(biāo)值函數(shù)是所有傳感器節(jié)點到Sink節(jié)點之間的總加權(quán)距離。用評價函數(shù)取F(x)評價每個染色體的適應(yīng)值大小，使得F(x)的值最小的解即可作為優(yōu)化算法的滿意解。目標(biāo)函數(shù)到適應(yīng)度函數(shù)的轉(zhuǎn)換為：

根據(jù)各染色體的適應(yīng)值的大小，采用賭輪盤法來選擇一些染色體進行遺傳操作[6]。一個染色體將被選擇的概率與其適應(yīng)值大小成正比。同時采用精英保留的選擇策略，將每次選擇時候出現(xiàn)的適應(yīng)值最小的染色體（當(dāng)前最好染色體）以概率1保留下來進行交叉和變異等遺傳操作。

3.3 遺傳操作算子

本文采用的是經(jīng)典的順序交叉算子[6]，每次運算將產(chǎn)生2個后代。

一種基于最近鄰方法設(shè)計的啟發(fā)式的變異算子[6]，用來產(chǎn)生更好的后代。一個父代通過改變鄰域內(nèi)的基因的序列來產(chǎn)生一組染色體。這些產(chǎn)生出來的染色體只留下適應(yīng)度最好的作為變異產(chǎn)生的后代。這里，原來的啟發(fā)式突變經(jīng)過改進，以提高種群的多樣性。所做的改進是將交換鄰域基因所產(chǎn)生的所有染色體都作為新生成的后代。

逆序變異算子：反轉(zhuǎn)變異操作是從父染色體中選擇一個子串序列，將子串序列反轉(zhuǎn)后生成一個后代。反轉(zhuǎn)變異操作只作用于一個染色體。除了在兩個染色體之間進行交換基因的特性之外它與啟發(fā)式變異非常相似。所以，反轉(zhuǎn)操作算子是一個變異遺傳操作，主要原因是這是用于增加種群的多樣性而非改善種群的質(zhì)量。

4 算法性能對比仿真及實驗分析

實驗對象：無線傳感器網(wǎng)絡(luò)監(jiān)控區(qū)域為100m×100m，傳感器節(jié)點數(shù)量為90，各個節(jié)點的位置分布和請求數(shù)分布為隨機值。預(yù)置的Sink節(jié)點數(shù)量P=8；遺傳算法的遺傳策略為：適應(yīng)值函數(shù)取最大值，啟發(fā)式變異率為0.05，交叉率取0.2。迭代次數(shù)取500。將Sink節(jié)點布局分別用枚舉法和本文提出的三鏈混合遺傳算法進行對比，效果圖如圖1所示。

圖1 多Sink節(jié)點布局圖對比

表3 兩種算法布局效果對比

由圖1可以看出，枚舉法和三鏈混合遺傳算法找到的布局位置有差異，表3數(shù)據(jù)比較了兩種算法在求加權(quán)距離最優(yōu)解的數(shù)據(jù)，包括總距離的大小和算法的效率、誤差率。由數(shù)據(jù)可以看出，枚舉法和三鏈混合遺傳算法在總加權(quán)距離上有一定的差別，但在算法執(zhí)行時間上有巨大的差異。并且三鏈混合遺傳算法在加權(quán)距離上的差異與枚舉法相比較可以算出其相對誤差，誤差率為10.7?？梢钥闯鋈溁旌线z傳算法在最優(yōu)解的求解和算法效率上都優(yōu)于枚舉法。

5 結(jié)語

本文主要應(yīng)用了三鏈混合遺傳算法來解決多Sink節(jié)點布局問題。首先介紹了無線傳感器網(wǎng)絡(luò)的內(nèi)容，詳細闡述了Sink節(jié)點布局的數(shù)學(xué)模型，并根據(jù)數(shù)學(xué)模型提出了三鏈混合遺傳算法。通過與枚舉法對比實驗分析，論證了三鏈混合遺傳算法在Sink節(jié)點布局上相對于枚舉法具有更優(yōu)的解及算法效率的提升?？梢娙溁旌线z傳算法在求解Sink節(jié)點布局最優(yōu)解上具有一定的優(yōu)勢。

[1]馬祖長，孫怡寧，梅濤．無線傳感器網(wǎng)絡(luò)綜述[J]．通信學(xué)報．2004，25(04)：114-124．

[2]潘耘，李嫣，李晉凱，等．無線傳感器網(wǎng)絡(luò)中的多Sink節(jié)點的放置問題[J]．計算機研究與發(fā)展，2010，47(S2)：92-95．

[3]王金鑫，賴旭芝，吳敏．一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)定位新算法[J]．計算技術(shù)與自動化，2007，26(04)：53-56．

[4]劉強，毛玉明，冷甦鵬，等．無線傳感器網(wǎng)絡(luò)中多Sink節(jié)點優(yōu)化部署方法[J]．計算機應(yīng)用，2011，31(9)：2313-2316．

[5]韓凱州，馬福昌．無線傳感器網(wǎng)絡(luò)中多Sink節(jié)點位置部署研究[J].傳感器與微系統(tǒng)，2014，33(3)：37-39．

[6]Gen M，Cheng R(1997)Genetic algorithms and engineering design [M]．Wiley，New York．

Sink Node Location Optimization for WSNs Based on Improved Three Chain Hybrid GeneticAlgorithm

Liu Yan
(Jiaying University,Meizhou 514015,Guangdong)

In the design and layout of Wireless Sensor Networks(WSNs),multiple Sink node locating is the key step in network topology.It is very important to control energy-consumption of network communication.By analyzing the layout of Sink node model,an improved three chain hybrid genetic algorithm is proposed to solve the Sink node's optimal location problem.The experimental results show that compared with the enumeration algorithm,the three chain hybrid genetic algorithm for the Sink node has better solutions and higher efficiency of the algorithm,which can reduce the energy consumption of wireless sensor networks and improve the network performance.

wireless sensor networks(WSNs);Sink node locating;three chain hybrid genetic algorithm

TP393

A

1008-6609(2016)08-0013-03

劉燕，女，湖南永州人，碩士，助理實驗師，研究方向：控制工程的理論與應(yīng)用研究。

廣東省教育廳創(chuàng)新強校工程重點平臺建設(shè)、培育項目，項目編號：2014KTSCX173；嘉應(yīng)學(xué)院自然科學(xué)研究項目，項目編號：314E23。