改進(jìn)人工魚群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化

張微微 楊海寧

（江蘇開放大學(xué) 江蘇省南京市 210036）

與普通的網(wǎng)絡(luò)相比，無(wú)線傳感器的網(wǎng)絡(luò)的自主性、靈活性更好一些，它的適用范圍更廣一些，在未來(lái)的生產(chǎn)應(yīng)用中具有更廣泛的前景。目前，在相對(duì)自然環(huán)境比較惡劣的地方通常部署著無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)，如果節(jié)點(diǎn)一旦出現(xiàn)故障問(wèn)題，我們?cè)趺锤玫母鼡Q節(jié)點(diǎn)，有些更換是人工無(wú)法完成的部分，那么怎么將節(jié)點(diǎn)合理的部署在應(yīng)用環(huán)境中就是我們迫切解決的問(wèn)題，也是我們研究的關(guān)鍵。傳感器覆蓋的優(yōu)化指的是在節(jié)點(diǎn)的部署上盡可能的使節(jié)點(diǎn)的分布達(dá)到最優(yōu)，這樣我們?cè)诒O(jiān)控?cái)?shù)據(jù)的時(shí)候可以更有效的對(duì)數(shù)據(jù)進(jìn)行收集。如果我們?cè)诓渴鸸?jié)點(diǎn)的時(shí)候用了過(guò)多的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，在傳輸過(guò)程中節(jié)點(diǎn)的能力容易耗盡，節(jié)點(diǎn)的計(jì)算能力也會(huì)由于傳輸受到局限性。通過(guò)檢測(cè)可以看出，由于節(jié)點(diǎn)之間存在著交叉，檢測(cè)的結(jié)果可以看出數(shù)據(jù)的重復(fù)，這樣影響數(shù)據(jù)的有效性，所以我們?cè)诓渴鸬臅r(shí)候不能用過(guò)多的節(jié)點(diǎn)，那么就需要我們來(lái)用盡可能少的節(jié)點(diǎn)來(lái)部署，同時(shí)我們還得保證無(wú)線傳感器網(wǎng)絡(luò)在正常工作的同時(shí)還要延長(zhǎng)生命周期，這個(gè)是目前研究的焦點(diǎn)。

作者查閱了相關(guān)文獻(xiàn)，了解到目前做無(wú)線傳感器方面研究的學(xué)者對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋做了非常深入的研究，科研成果顯著。有學(xué)者提出基于能量的無(wú)線傳感器網(wǎng)絡(luò)路由策略，作者設(shè)計(jì)了規(guī)則網(wǎng)絡(luò)模型和隨機(jī)網(wǎng)絡(luò)模型。文中提出的規(guī)則網(wǎng)絡(luò)模型就是在一個(gè)二維的平面內(nèi)，規(guī)則的排列著節(jié)點(diǎn)，通過(guò)作者的分析得出，這個(gè)規(guī)則的網(wǎng)絡(luò)模型太過(guò)于理想化，在實(shí)踐中，網(wǎng)絡(luò)節(jié)點(diǎn)的投放方式多采用飛機(jī)的隨機(jī)投放，采用這樣的投放方法在實(shí)際應(yīng)用中受投放當(dāng)日的風(fēng)向、濕度等實(shí)際環(huán)境的影響較大，我們多期待的理想效果很難達(dá)到。在網(wǎng)絡(luò)環(huán)境中隨機(jī)的擺放節(jié)點(diǎn)稱為隨機(jī)網(wǎng)絡(luò)模型，在代碼中現(xiàn)為每個(gè)節(jié)點(diǎn)生成監(jiān)測(cè)范圍，這種情況更接近于實(shí)際情況。在無(wú)線傳感器的策略設(shè)計(jì)中通過(guò)對(duì)路由算法的分析設(shè)計(jì)實(shí)現(xiàn)了路由算法，通過(guò)作者的一系列仿真結(jié)果可以看出：在同等的條件下，分配初始能量的網(wǎng)絡(luò)生命周期比按度分配初始能量的更長(zhǎng)，確定路由比概率路由具有更好的數(shù)據(jù)傳輸特性，路由參數(shù)對(duì)確定路由數(shù)據(jù)傳輸?shù)恼{(diào)節(jié)作用比概率路由更明顯。通過(guò)相關(guān)文獻(xiàn)的查詢，還有學(xué)者提出用改進(jìn)的人工蜂群算法來(lái)優(yōu)化無(wú)線傳感器的覆蓋。由于傳統(tǒng)算法普遍存在節(jié)點(diǎn)覆蓋率較低的情況，要想實(shí)現(xiàn)全局優(yōu)化在技術(shù)層面還比較難以實(shí)現(xiàn)，無(wú)線傳感器的網(wǎng)絡(luò)結(jié)構(gòu)和群體智能算法很接近，所以該學(xué)者在研究中采用了改進(jìn)的蜂群算法來(lái)優(yōu)化無(wú)線傳感器的覆蓋。該學(xué)者改進(jìn)了人工蜂群算法，解決了網(wǎng)絡(luò)覆蓋的優(yōu)化問(wèn)題。通過(guò)實(shí)驗(yàn)可以看出，不管在節(jié)點(diǎn)較多還是節(jié)點(diǎn)較少的時(shí)候，改進(jìn)的算法都有優(yōu)化傳感器網(wǎng)絡(luò)的覆蓋率，具有更優(yōu)的節(jié)點(diǎn)利用率，達(dá)到了研究目的。有學(xué)者提出在復(fù)雜環(huán)境下一種多移動(dòng)節(jié)點(diǎn)的WSN 三維覆蓋算法，該覆蓋算法主要針對(duì)偏遠(yuǎn)山地復(fù)雜地形，提出來(lái)多移動(dòng)節(jié)點(diǎn)的WSN三維覆蓋算法，可以有效探測(cè)覆蓋空洞，利用移動(dòng)節(jié)點(diǎn)有效修復(fù)，降低網(wǎng)絡(luò)能耗。隨著無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用在實(shí)際應(yīng)用中的不斷深入，尤其在大數(shù)據(jù)環(huán)境下，例如啟發(fā)式算法的缺陷不斷涌現(xiàn)出來(lái)，如果求解效率，時(shí)間長(zhǎng)等。

1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的原理

1.1 節(jié)點(diǎn)的覆蓋優(yōu)化原理

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的原理是：首先，在大數(shù)據(jù)環(huán)境的整個(gè)無(wú)線網(wǎng)絡(luò)傳感器的區(qū)域中，在視線范圍內(nèi)的稱為監(jiān)控區(qū)域，在這個(gè)監(jiān)控區(qū)域中劃分為無(wú)數(shù)多個(gè)小區(qū)域，這個(gè)小區(qū)域稱為子區(qū)域；其次，在每個(gè)劃分的子區(qū)域中用改進(jìn)的人工魚群算法對(duì)整個(gè)區(qū)域的節(jié)點(diǎn)覆蓋進(jìn)行求解，最后，對(duì)人工魚群算法中求得的結(jié)果采用Map/Reduce 機(jī)制，利用該機(jī)制產(chǎn)生的結(jié)果進(jìn)行融合。

1.2 Map/Reduce的機(jī)制

在大數(shù)據(jù)環(huán)境的整個(gè)無(wú)線網(wǎng)絡(luò)傳感器的區(qū)域中分布著規(guī)模龐大的網(wǎng)絡(luò)節(jié)點(diǎn)，在這么多數(shù)量的節(jié)點(diǎn)中，如果采用一臺(tái)計(jì)算機(jī)對(duì)整個(gè)監(jiān)控區(qū)域的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行求解，處理的數(shù)據(jù)量是相當(dāng)大的，處理數(shù)據(jù)所消耗的時(shí)間也是很漫長(zhǎng)，完成的效率比較低下，無(wú)法滿足當(dāng)前的工作需要以及節(jié)點(diǎn)覆蓋的要求，Map/Reduce 的機(jī)制就是將這類數(shù)據(jù)量大的網(wǎng)絡(luò)傳感器劃分為多個(gè)子片，在所劃分的子片中對(duì)每個(gè)子問(wèn)題來(lái)求解，與其對(duì)應(yīng)的每個(gè)子問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)來(lái)完成計(jì)算，計(jì)算結(jié)果通過(guò)Map/Reduce 的機(jī)制果進(jìn)行融合，通過(guò)這樣的方法可以很快解決每個(gè)節(jié)點(diǎn)在運(yùn)行中的缺陷。

2 傳感器節(jié)點(diǎn)覆蓋的優(yōu)化策略

2.1 節(jié)點(diǎn)覆蓋優(yōu)化的目標(biāo)函數(shù)

在這里我們?cè)O(shè)在整個(gè)無(wú)線網(wǎng)絡(luò)傳感器的區(qū)域中分布的網(wǎng)絡(luò)節(jié)點(diǎn)都分布在一個(gè)矩形區(qū)域，這里做一個(gè)極端的假設(shè)為所有分布的節(jié)點(diǎn)都是性能相同的節(jié)點(diǎn)，所有的節(jié)點(diǎn)都是以自己為中心點(diǎn)，所有的節(jié)點(diǎn)他們都在通信半徑為R 的圓內(nèi)，其中，每個(gè)節(jié)點(diǎn)的坐標(biāo)都為(a,b)，矩形區(qū)域中分布的節(jié)點(diǎn)i，設(shè)在該事件中所覆蓋的坐標(biāo)事件為fi，那么如下所示：

在整個(gè)無(wú)線傳感器節(jié)點(diǎn)(a,b)的覆蓋概率為c(0,j)，則公式為：

所以在整個(gè)無(wú)線傳感器節(jié)點(diǎn)覆蓋面積就是全部節(jié)點(diǎn)覆蓋面積的并集(wcover)，則公式為：

傳感器網(wǎng)絡(luò)覆蓋率f1和節(jié)點(diǎn)利用率f2計(jì)算公式具體如下：

在公式中，w 為事件中節(jié)點(diǎn)的總數(shù)，w’是假設(shè)工作的節(jié)點(diǎn)數(shù)。

由于整個(gè)無(wú)線網(wǎng)絡(luò)傳感器的區(qū)域中分布的節(jié)點(diǎn)在工作中會(huì)有受到能量的有限性，所以我們必須要考慮的一個(gè)問(wèn)題就是在整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的工作的矩形區(qū)域內(nèi)節(jié)點(diǎn)能量消耗的均衡，這樣我們定義能量消耗均衡函數(shù)為：

該式子中，Ei設(shè)為節(jié)點(diǎn)中的剩余能量。

所以無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的覆蓋所優(yōu)化的目標(biāo)函數(shù)是：

其中，q1、q2、q3為權(quán)值。

2.2 人工魚群算法解析

《Swarm intelligence:From Natural to Artificial System》中對(duì)群智能進(jìn)行了詳細(xì)的論述和分析了：任何一種由昆蟲群體和其他動(dòng)物社會(huì)行為機(jī)制而激發(fā)和設(shè)計(jì)出的算法或分布解決問(wèn)題的策略均屬于群智能。魚群是Swarm 的典型例子。在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)中，利用人工魚群算法來(lái)模擬魚群的日常活動(dòng)，魚群在自然環(huán)境中游行，需要不斷的適應(yīng)周圍的環(huán)境，這樣魚群就需要調(diào)整自身游行的狀態(tài)，每個(gè)魚群與魚群之間需要通過(guò)相互協(xié)作，在不斷的搜索中找到根本問(wèn)題的求解。

人工魚群算法就是利用魚群在不斷調(diào)整游行狀態(tài)中的尋找優(yōu)化模式模仿魚群的覓食行為，分別為：魚群的覓食、魚群的聚群行為、魚群的追尾行為。

（1）魚群的覓食行為：指的是魚追著食物多的方向游動(dòng)的一種行為，人工魚Xi 在其視野范圍內(nèi)隨機(jī)選擇一個(gè)將來(lái)的狀態(tài)Xj，分別計(jì)算他們的目標(biāo)函數(shù)進(jìn)行比較，如果發(fā)現(xiàn)Xj 比Xi 的方向優(yōu)秀，那么Xi 就往Xj 方向游動(dòng)，否則Xi 繼續(xù)停留在其視野范圍內(nèi)，反復(fù)嘗試后仍然沒(méi)有滿足的條件后，則隨機(jī)移動(dòng)使Xi 達(dá)到一個(gè)新的狀態(tài)搜索。

（2）魚群的聚群行為（AF—swarm）：魚群在游動(dòng)過(guò)程中為了保證自身的生存安全和躲避危害會(huì)自然的聚集成群。一般遵守的規(guī)則為：一是分隔規(guī)則，就是盡量避免與鄰近伙伴過(guò)于擁擠，二是對(duì)準(zhǔn)規(guī)則，就是盡量與自己鄰近的伙伴在一致的方向游動(dòng)，三是內(nèi)聚規(guī)則，就是盡量朝著鄰近伙伴的中心游動(dòng)。假設(shè)人工魚群Xi 搜索其視野范圍內(nèi)的伙伴數(shù)為nf 及中心位置為Xc，若Yc/nf＞δ×Yi，表明魚群的中心位置狀態(tài)比較好不擁擠，則Xi 朝著魚群的中心位置移動(dòng)一步，否則執(zhí)行覓食行為。

（3）魚群的追尾行為（AF—follow）：指的是魚向它的可視范圍內(nèi)最優(yōu)化的區(qū)域游動(dòng)的一種行為。人工魚Xi 搜索在它的可視范圍內(nèi)所有伙伴中最優(yōu)的魚伙伴Xj，如果Yj/nf＞δYi，表明最優(yōu)魚伙伴的周圍不太擁擠，則Xi 朝著該伙伴周圍移動(dòng)一步，否則執(zhí)行覓食行為。

（4）公告板：記錄最優(yōu)魚個(gè)體狀態(tài)的地方。每條人工魚在完成自身迭代后，將自身的狀態(tài)與公告板上記錄的狀態(tài)進(jìn)行比較，如果優(yōu)于公告板上記錄的狀態(tài)則將最優(yōu)狀態(tài)記錄在公告板上，替換以前記錄的狀態(tài)，否則原公告板上的狀態(tài)不變。在整個(gè)算法迭代結(jié)束后，公告板上輸出的值就是我們算的最優(yōu)值。

2.3 利用魚群算法在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋所優(yōu)化的步驟

第一步：將大數(shù)據(jù)下傳感器網(wǎng)絡(luò)初始化，并對(duì)人工魚群算法的參數(shù)進(jìn)行初始化；

第二步：計(jì)算初始魚群的個(gè)體的適應(yīng)值，并對(duì)整個(gè)人工魚群的狀態(tài)進(jìn)行評(píng)估，將最優(yōu)魚人工魚狀態(tài)記錄到人告板。

第三步：通過(guò)模擬人工魚的覓食、聚群、追尾等行為，找到最優(yōu)的食物濃度，更新自己生成新魚群。

第四步：在搜索中所有的人工魚群都完成后，人工魚群的狀態(tài)需要重新估計(jì)，估計(jì)后的狀態(tài)與第二步中記錄的公告板中的人工魚群狀態(tài)進(jìn)行比較，兩者比較后結(jié)果選取更優(yōu)化的結(jié)果作為公告板的最新狀態(tài)。

第五步：觀察公告板上的狀態(tài)，當(dāng)公告板上的記錄的狀態(tài)達(dá)到了最優(yōu)狀態(tài)，也就是結(jié)果達(dá)到了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的要求了，那么人工魚群算法的搜索過(guò)程就結(jié)束了，否則返回到第三步繼續(xù)進(jìn)行搜索。

3 總結(jié)

大數(shù)據(jù)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋優(yōu)化問(wèn)題是我們解決的問(wèn)題，本文提出了一種在改進(jìn)的魚群算法。首先提出了Map/Reduce 的機(jī)制，該機(jī)制就是將這類數(shù)據(jù)量大的網(wǎng)絡(luò)傳感器劃分為多個(gè)片來(lái)完成，每個(gè)子問(wèn)題在相對(duì)應(yīng)的節(jié)點(diǎn)內(nèi)完成，最后將各個(gè)節(jié)點(diǎn)完成的結(jié)果進(jìn)行融合，這樣解決了每個(gè)節(jié)點(diǎn)的缺陷。然后通過(guò)人工魚群算法對(duì)子網(wǎng)絡(luò)中節(jié)點(diǎn)覆蓋優(yōu)化問(wèn)題進(jìn)行求解，根據(jù)魚群算法的計(jì)算的結(jié)果可以說(shuō)明：

（1）在Map/Reduce 機(jī)制下將大數(shù)據(jù)環(huán)境下的傳感器網(wǎng)絡(luò)進(jìn)行分片的逐步細(xì)化，這樣有助于求解的簡(jiǎn)單方便，而且還將傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋效率大大提高，實(shí)現(xiàn)了大數(shù)據(jù)環(huán)境下的傳感器節(jié)點(diǎn)覆蓋優(yōu)化。

（2）采用人工魚群算法對(duì)傳感器節(jié)點(diǎn)覆蓋優(yōu)化問(wèn)題進(jìn)行求解，可以提高了傳感器節(jié)點(diǎn)覆蓋率，可以滿足傳感器節(jié)點(diǎn)覆蓋的要求。