周　杰，田　敏，鐘福如

（石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，新疆　石河子 332003）

基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)高能效分簇方法*

周杰，田敏，鐘福如

（石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，新疆石河子 332003）

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量通常由能量有限的電池供應(yīng)，如何在對(duì)節(jié)點(diǎn)進(jìn)行分簇的同時(shí)減小通信能耗是研究中的一個(gè)重要問(wèn)題。提出了一種基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)能量高效分簇方法，通過(guò)智能選取簇頭位置來(lái)降低無(wú)線傳感器網(wǎng)絡(luò)的單輪通信能耗。在不同節(jié)點(diǎn)數(shù)和簇頭比例的條件下，分別采用了粒子群算法、量子遺傳算法、模擬退火算法和混沌小生境狼群算法進(jìn)行了無(wú)線傳感器網(wǎng)絡(luò)分簇。仿真結(jié)果表明，基于混沌小生境狼群算法的無(wú)線傳感器網(wǎng)絡(luò)分簇能夠有效降低無(wú)線傳感器網(wǎng)絡(luò)的整體單輪通信能耗和平均節(jié)點(diǎn)通信能耗，有效提升了能量利用效率。

通信與信息系統(tǒng)；無(wú)線傳感器網(wǎng)絡(luò)；人工智能；狼群算法；分簇

1　概述

隨著集成電路、微機(jī)電系統(tǒng)、SoC技術(shù)、無(wú)線電通信和的發(fā)展，融合了嵌入式技術(shù)，無(wú)線網(wǎng)絡(luò)通信技術(shù)，計(jì)算技術(shù)和分布式信息處理技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)（WirelessSensorNetworks，WSNs）成為了研究熱點(diǎn)，受到了越來(lái)越多重視［1］。無(wú)線傳感器網(wǎng)絡(luò)（WSNs）是由大量具有計(jì)算功能、存儲(chǔ)功能和通信功能的微型智能節(jié)點(diǎn)以自組織的形式組成的分布式新型感知網(wǎng)絡(luò)［2］。每個(gè)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)通常由感知模塊、存儲(chǔ)模塊、嵌入式處理器模塊、射頻通信模塊及電源模塊等多部分組成，有時(shí)還配有執(zhí)行模塊和定位模塊［3］。隨著技術(shù)的逐漸成熟，無(wú)線傳感器網(wǎng)絡(luò)（WSNs）已經(jīng)越來(lái)越深入到智能交通、智能醫(yī)療、工業(yè)應(yīng)用、災(zāi)難救助、環(huán)境監(jiān)測(cè)、安全保衛(wèi)以及家庭和辦公環(huán)境監(jiān)控等生活各個(gè)方面，在民用和軍事領(lǐng)域均具有廣泛的應(yīng)用［4］。

在無(wú)線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)覆蓋和通信能耗問(wèn)題是研究中的兩個(gè)核心問(wèn)題，網(wǎng)絡(luò)覆蓋決定了無(wú)線傳感器網(wǎng)絡(luò)對(duì)周圍環(huán)境的監(jiān)測(cè)質(zhì)量，通信能耗則決定了無(wú)線傳感器網(wǎng)絡(luò)的能量利用效率。研究表明，合理的傳感器節(jié)點(diǎn)分簇能夠明顯地降低網(wǎng)絡(luò)的通信消耗，同時(shí)提高能量利用效率［5］。然而，傳感器網(wǎng)絡(luò)由隨機(jī)撒布的大量的傳感器節(jié)點(diǎn)組成，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量龐大、網(wǎng)絡(luò)整體通信能耗較高，因此，有效節(jié)約能量，延長(zhǎng)網(wǎng)絡(luò)的生命周期是無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)的首要目標(biāo)［6］。

然而，一些高密度無(wú)線傳感器網(wǎng)絡(luò)中大量傳感器節(jié)點(diǎn)分布密集，導(dǎo)致網(wǎng)絡(luò)分簇需要消耗較高的算法復(fù)雜度［7］。同時(shí)，大多數(shù)分簇算法均關(guān)注于傳感器網(wǎng)絡(luò)的多輪能耗問(wèn)題，而對(duì)于如何降低無(wú)線傳感器網(wǎng)絡(luò)的單輪能耗研究較少。部分無(wú)線傳感器網(wǎng)絡(luò)采用固定電源供電，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)眾多導(dǎo)致整體能耗較大，長(zhǎng)時(shí)間運(yùn)行費(fèi)用較高，同時(shí)網(wǎng)絡(luò)的通信能耗對(duì)分簇結(jié)果敏感。因此，傳統(tǒng)的網(wǎng)絡(luò)分簇方法已經(jīng)不能適用于采用固定電源供電的高密度無(wú)線傳感器網(wǎng)絡(luò)，需要通過(guò)設(shè)計(jì)全新的啟發(fā)式算法來(lái)解決這一問(wèn)題。

2　系統(tǒng)模型

在高密度傳感器網(wǎng)絡(luò)中，不同傳感器之間距離較近，不同節(jié)點(diǎn)之間容易產(chǎn)生通信干擾，因此通常采用分簇的方法將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)簇，每個(gè)簇內(nèi)選出一個(gè)簇頭節(jié)點(diǎn)。簇內(nèi)節(jié)點(diǎn)感知到的信息先通過(guò)單跳方式發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)通常具有較強(qiáng)的數(shù)據(jù)處理能力，簇頭節(jié)點(diǎn)將簇內(nèi)節(jié)點(diǎn)感知到的節(jié)點(diǎn)經(jīng)過(guò)數(shù)據(jù)融合后發(fā)送給網(wǎng)關(guān)節(jié)點(diǎn)。網(wǎng)關(guān)節(jié)點(diǎn)在接收到數(shù)據(jù)后再將數(shù)據(jù)傳輸給用戶，并由用戶將數(shù)據(jù)解析成適當(dāng)?shù)母袷竭M(jìn)行處理。如果用戶需要對(duì)節(jié)點(diǎn)的參數(shù)進(jìn)行設(shè)置，就要執(zhí)行相反的一套流程，即用戶首先把需要下發(fā)的控制指令和參數(shù)傳送給網(wǎng)關(guān)節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)通過(guò)無(wú)線通信方式下發(fā)相關(guān)指令和控制參數(shù)給各個(gè)簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)再將控制信息下發(fā)給感知節(jié)點(diǎn)。

由于無(wú)線傳感器網(wǎng)絡(luò)通常采用電池供電，且更換電池需要耗費(fèi)較高成本，能耗控制問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)控制中的一個(gè)重要問(wèn)題。研究表明，無(wú)線傳感器網(wǎng)絡(luò)中超過(guò)一半的能量消耗在無(wú)線通信產(chǎn)生的數(shù)據(jù)傳輸上。如果能夠有效減少通信能耗，就能夠延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的壽命，減少更換電池產(chǎn)生的人工成本。

通信能耗通常由發(fā)送能耗和接收能耗構(gòu)成。發(fā)送能耗和接收可以由如下公式算出：

式中，costs（k，d）為傳輸k比特?cái)?shù)據(jù)到距離為d的節(jié)點(diǎn)所消耗的能量，εamp是功率放大參數(shù)（power amplificationparameter），Eelec為電子能量 參數(shù)（electronicsenergyparameter），d是節(jié)點(diǎn)間的距離。n的取值由具體的通行環(huán)境決定。在本文中取n=3。

3　基于混沌小生境狼群算法的無(wú)線傳感器網(wǎng)絡(luò)高能效分簇

3.1狼群算法簡(jiǎn)介

狼群算法屬于人工智能（artificialintelligence，AI）的范疇。與常用的遺傳算法和粒子群算法類似，狼群算法也是受到了生物學(xué)現(xiàn)象的啟發(fā)而被設(shè)計(jì)出來(lái)的一種迭代優(yōu)化算法。原始的遺傳算法通常存在早熟收斂、進(jìn)化停滯等缺陷。問(wèn)題的解被抽象成為人工狼，而根據(jù)人工狼優(yōu)劣程度的優(yōu)勝劣汰就是算法迭代的基礎(chǔ)。狼群算法通過(guò)個(gè)體狼之間的合理分工和相互配合，相比傳統(tǒng)的遺傳算法和模擬退火算法能夠有效提升算法進(jìn)化速度，在迭代次數(shù)相同的情況下得到較優(yōu)的結(jié)果。

Yang等人首先提出了狼群算法。通過(guò)研究自然界中狼群的捕食習(xí)性，并以此為依據(jù)抽象出了狼群算法的具體實(shí)現(xiàn)步驟。在狼群中任何時(shí)刻均存在一只唯一的頭狼，而頭狼不是一成不變的。在每一次算法迭代之前，狼群中較為優(yōu)秀的幾只游獵狼會(huì)通過(guò)競(jìng)爭(zhēng)決定頭狼的歸屬。狼群中存在一定數(shù)量的游獵狼，游獵狼在一定范圍內(nèi)進(jìn)行搜索，尋找獵物的位置。在通過(guò)競(jìng)爭(zhēng)選出頭狼后，狼群中的所有狼會(huì)向頭狼靠近。最后，在每次圍獵后，狼群淘汰一定比例最弱的狼，并隨機(jī)生成新的狼崽來(lái)對(duì)被淘汰的狼進(jìn)行補(bǔ)充。

3.2人工狼群的小生境劃分與混沌初始化

在基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)高能效分簇方法中，人工狼的編碼可用二進(jìn)制向量表示，“1”表示對(duì)應(yīng)位置為簇頭節(jié)點(diǎn)，而數(shù)字“0”表示感知節(jié)點(diǎn)。例如，網(wǎng)絡(luò)中有8個(gè)節(jié)點(diǎn)，個(gè)體編碼為“00101011”，則代表3號(hào)、5號(hào)、7號(hào)和8號(hào)節(jié)點(diǎn)為簇頭節(jié)點(diǎn)，其余節(jié)點(diǎn)為感知節(jié)點(diǎn)。

為了加快進(jìn)化速度，在混沌小生境狼群算法中，狼群被分為多個(gè)子狼群，同時(shí)每個(gè)人工狼均由混沌映射生成。這樣，各個(gè)子狼群中的頭狼不相互干擾，從而避免了單一頭狼引發(fā)的早熟收斂現(xiàn)象。此外，混沌映射加強(qiáng)了狼群生成的隨機(jī)性，從而加速了狼群的進(jìn)化速度。

每頭人工狼由下式所示的Logistic混沌映射產(chǎn)生。

當(dāng)時(shí)μ=4，Logistic映射處于混沌狀態(tài)。在初始個(gè)體生成后，按照比例將映射值最高的位置初始化為“1”，其余位置初始化為“0”。

隧道排煙設(shè)計(jì)，考慮排煙區(qū)段較長(zhǎng)，隧道設(shè)排煙豎井一座，設(shè)置在樁號(hào)K104+439與K104+430左右線中間處，豎井井口標(biāo)高926 m，井深88 m，成井直徑5.20 m，最大開(kāi)挖直徑6.52 m(包含5 cm預(yù)留變形量)，距離右線出口761 m。兩隧道均設(shè)置排煙橫洞與之連接。豎井正常情況下不啟用，僅在火災(zāi)情況下視火災(zāi)發(fā)生的不同部位結(jié)合防災(zāi)預(yù)案正確開(kāi)啟來(lái)排煙，排煙區(qū)段分4 900 m和800 m兩個(gè)區(qū)段排煙。

3.3探狼探索

人工狼群中除頭狼外，適應(yīng)度較優(yōu)的N頭人工狼被視為探狼。探狼在自身周圍的指定步數(shù)內(nèi)進(jìn)行隨機(jī)探索。隨機(jī)性借助Logistic混沌映射進(jìn)行實(shí)現(xiàn)。

3.4頭狼選擇與頭狼召喚

在探狼探索完成后，所有探狼與上一次迭代產(chǎn)生的頭狼共同競(jìng)爭(zhēng)本代頭狼的位置。所有探狼和上一代頭狼中適應(yīng)度最高的人工狼將成為本代頭狼。人工狼的優(yōu)秀程度由如下所示的適應(yīng)度函數(shù)計(jì)算得出：

其中Fit（E）為通信能耗，而costs和costr的計(jì)算依據(jù)式（1）和式（2）。

在選出頭狼后，狼群中其余的人工狼均向頭狼的方向靠攏，靠攏的步數(shù)隨機(jī)，隨機(jī)性同樣借助Logistic混沌映射進(jìn)行實(shí)現(xiàn)。

按比例淘汰狼群中適應(yīng)度最差的30%的人工狼，借助Logistic映射隨機(jī)生成相等數(shù)量的新人工狼取而代之。

3.6算法終止條件

算法運(yùn)行達(dá)到預(yù)先設(shè)定的指定迭代次數(shù)后終止。

4　仿真與分析

本文采用MATLAB軟件對(duì)基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)分簇方法進(jìn)行了仿真模擬。高密度無(wú)線傳感器網(wǎng)絡(luò)布設(shè)范圍設(shè)定為100m×100m的矩形區(qū)域，所有高密度傳感器節(jié)點(diǎn)在布設(shè)范圍內(nèi)均勻隨機(jī)分布。網(wǎng)關(guān)節(jié)點(diǎn)被布置在區(qū)域的中心，坐標(biāo)為（50，50）。統(tǒng)計(jì)發(fā)現(xiàn)，在實(shí)際系統(tǒng)中上行傳輸?shù)谋O(jiān)測(cè)數(shù)據(jù)量遠(yuǎn)大于下行傳輸?shù)目刂茢?shù)據(jù)量，因此本文在仿真中僅考慮下行數(shù)據(jù)傳輸。仿真中傳輸?shù)臄?shù)據(jù)量取1M比特，傳輸?shù)膶?shí)際能耗由公式（1）和公式（2）來(lái)計(jì)算。εamp取100pJ/bit/m2，εamp取50nJ/bit，n取值為3。

作為對(duì)比，本文還在相同參數(shù)情況下對(duì)遺傳算法和模擬退火算法進(jìn)行了仿真。在所有三種仿真中，算法的最大迭代次數(shù)均設(shè)定為100次，種群中的個(gè)體數(shù)量均取50。仿真后通信能耗隨算法迭代次數(shù)的變化情況如圖1所示：

圖1　網(wǎng)絡(luò)通信能耗隨算法迭代次數(shù)的變化

圖1是高密度傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為200個(gè)，簇頭節(jié)點(diǎn)占總結(jié)點(diǎn)數(shù)比率為10%時(shí)，基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)分簇方法，基于遺傳算法的分簇方法及基于模擬退火算法的分簇方法進(jìn)行分簇后，無(wú)線傳感器網(wǎng)絡(luò)通信總能耗隨算法迭代次數(shù)的變化圖。從圖中可以看出，基于模擬退火算法的分簇方法在進(jìn)化過(guò)程中容易陷入進(jìn)化停滯，200次迭代后的最終通信能耗較高?；谶z傳算法的分簇方法性能優(yōu)于模擬退火算法，但由于產(chǎn)生了早熟收斂現(xiàn)象，通信能耗依然較高?；诨煦缧∩忱侨核惴ǖ母呙芏葻o(wú)線傳感器網(wǎng)絡(luò)分簇方法通過(guò)人工狼的游獵和圍攻等步驟，有效避免了早熟收斂和進(jìn)化停滯現(xiàn)象，最終通信能耗較低。

圖2為高密度傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為200個(gè)，簇頭節(jié)點(diǎn)占總結(jié)點(diǎn)數(shù)比率為10%時(shí)，基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)分簇結(jié)果圖。從圖中可以看出，簇頭分布較為均勻，簇頭距離簇內(nèi)成員節(jié)點(diǎn)距離較短，通信能量消耗相對(duì)較小。

圖2　分簇結(jié)果圖

5　結(jié)論

本文提出了一種基于混沌小生境狼群算法的高密度無(wú)線傳感器網(wǎng)絡(luò)高能效分簇方法，通過(guò)智能選取簇頭位置來(lái)降低無(wú)線傳感器網(wǎng)絡(luò)的單輪通信能耗。在不同節(jié)點(diǎn)數(shù)和簇頭比例的條件下，分別采用了粒子群算法、量子遺傳算法、模擬退火算法和混沌小生境狼群算法進(jìn)行了無(wú)線傳感器網(wǎng)絡(luò)分簇。仿真結(jié)果表明，基于混沌小生境狼群算法的無(wú)線傳感器網(wǎng)絡(luò)分簇能夠有效降低無(wú)線傳感器網(wǎng)絡(luò)的整體單輪通信能耗和平均節(jié)點(diǎn)通信能耗，有效提升了能量利用效率。

［1］ PeiH，LiX，Soltani，S，et al.The Evolution of MAC Protocols in Wireless Sensor Networks：A Survey［J］.IEEE Communications Surveys&Tutorials，2013，15（1）：101-120.

［2］ Esch，J.A Survey on Topology Control in Wireless Sensor Networks：Taxonomy，Comparative Study，and Open Issues ［J］.Proceedings of the IEEE，2013，101（12）：2534-2537.

［3］ Mo L，Zhenjiang L，Vasilakos A V.A Survey on Topology Control in Wireless Sensor Networks：Taxonomy，Comparative Study，and Open Issues［J］.Proceedings of the IEEE，2013，101（12）：2538-2557.

［4］ 李曉維.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京：北京理工大學(xué)出版社，2007.

［5］ 崔遜學(xué).無(wú)線傳感器網(wǎng)絡(luò)簡(jiǎn)明教程［M］.北京：清華大學(xué)出版社，2009.

［6］ 王良民，廖聞劍.無(wú)線傳感器網(wǎng)絡(luò)可生存理論與技術(shù)研究［M］.北京：人民郵電出版社，2011.

［7］ Demigha O.，Hidouci W.K，Ahmed，T.On Energy Efficiency in Collaborative Target Tracking in Wireless Sensor Network：A Review［J］.IEEE Communications Surveys&Tutorials，2013，15（3）：1210-1222.

TN929.5

石河子大學(xué)高層次人才科研啟動(dòng)項(xiàng)目（編號(hào)RCZX201530）。