劉燕

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

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

劉燕

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

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

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

1 引言

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

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

2 問(wèn)題描述

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

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

表1 問(wèn)題變量定義表

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

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

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

同時(shí)，此問(wèn)題還需要滿足以下條件，如表2所示：

表2 問(wèn)題滿足的條件

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

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

3.1 染色體編碼

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

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

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

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

3.3 遺傳操作算子

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

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

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

4 算法性能對(duì)比仿真及實(shí)驗(yàn)分析

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

圖1 多Sink節(jié)點(diǎn)布局圖對(duì)比

表3 兩種算法布局效果對(duì)比

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

5 結(jié)語(yǔ)

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

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

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

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

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

[5]韓凱州，馬福昌．無(wú)線傳感器網(wǎng)絡(luò)中多Sink節(jié)點(diǎn)位置部署研究[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

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

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