基于三鏈混合遺傳算法的WSNs中Sink節點布局優化

劉燕

（嘉應學院電子信息工程學院，廣東 梅州 514015）

基于三鏈混合遺傳算法的WSNs中Sink節點布局優化

劉燕

（嘉應學院電子信息工程學院，廣東 梅州 514015）

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

無線傳感器網絡；Sink節點布局；三鏈混合遺傳算法

1 引言

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

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

2 問題描述

Sink節點的布局與無線傳感器網絡的服務性能緊密相關。可以認為無線傳感器網絡中的Sink節點與傳感器節點之間存在服務與被服務的關系。由于無線通信鏈路可靠性及服務效率與服務點與被服務點之間的距離有關，因此縮短Sink節點與傳感器節點之間的距離是一種提高服務效率的有效策略。

于是，對于一個具體的無線傳感器網絡環境作如下定義：

表1 問題變量定義表

則問題為在給定區域內，從M個候選Sink節點位置中找出P個Sink節點的位置，使得所有傳感器節點到Sink節點之間的總加權距離最小化。加權值為節點i單位時間發送的請求數ri。

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

Tij=傳感器節點i被匯節點j服務其他 （1）

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

表2 問題滿足的條件

3 遺傳算法實現

Sink節點候選位置可以采用網格方法，將區域用網格劃分，Sink節點布局在網格的交叉點上。針對不同的布局要求，網格的密度可以適應性改變。

3.1 染色體編碼

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

3.2 適應值函數和選擇操作

針對上一節提出的數學模型，目標值函數是所有傳感器節點到Sink節點之間的總加權距離。用評價函數取F(x)評價每個染色體的適應值大小，使得F(x)的值最小的解即可作為優化算法的滿意解。目標函數到適應度函數的轉換為：

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

3.3 遺傳操作算子

本文采用的是經典的順序交叉算子[6]，每次運算將產生2個后代。

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

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

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

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

圖1 多Sink節點布局圖對比

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

由圖1可以看出，枚舉法和三鏈混合遺傳算法找到的布局位置有差異，表3數據比較了兩種算法在求加權距離最優解的數據，包括總距離的大小和算法的效率、誤差率。由數據可以看出，枚舉法和三鏈混合遺傳算法在總加權距離上有一定的差別，但在算法執行時間上有巨大的差異。并且三鏈混合遺傳算法在加權距離上的差異與枚舉法相比較可以算出其相對誤差，誤差率為10.7。可以看出三鏈混合遺傳算法在最優解的求解和算法效率上都優于枚舉法。

5 結語

本文主要應用了三鏈混合遺傳算法來解決多Sink節點布局問題。首先介紹了無線傳感器網絡的內容，詳細闡述了Sink節點布局的數學模型，并根據數學模型提出了三鏈混合遺傳算法。通過與枚舉法對比實驗分析，論證了三鏈混合遺傳算法在Sink節點布局上相對于枚舉法具有更優的解及算法效率的提升。可見三鏈混合遺傳算法在求解Sink節點布局最優解上具有一定的優勢。

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

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

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

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

[5]韓凱州，馬福昌．無線傳感器網絡中多Sink節點位置部署研究[J].傳感器與微系統，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

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

廣東省教育廳創新強校工程重點平臺建設、培育項目，項目編號：2014KTSCX173；嘉應學院自然科學研究項目，項目編號：314E23。