一種基于仿生算法的傳感器網(wǎng)絡協(xié)議研究

摘要：為了降低無線傳感器網(wǎng)絡的能耗提出了將仿生算法應用于網(wǎng)絡路由決策，生成節(jié)點之間的最優(yōu)化路由。給出了仿生算法的基本原理與計算最小路徑樹的主要步驟。實驗結果顯示，該算法相對于PVCHI等協(xié)議來說，有較好的降低網(wǎng)絡節(jié)點工作能耗的效果。

關鍵詞：簇;仿生路由算法;最短路徑樹

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）04-0177-02

Abstract：This paper proposes a method to reduce the energy consumption of nodes by applying bionic algorithm to network routing decision to generate the optimal routing between nodes. The basic principle of bionic algorithm and the main steps of calculating the minimum path number are given. The experimental results show that the algorithm can effectively reduce energy consumption.

Key words：cluster; bionic routing algorithm; shortest path tree

1背景

無線傳感器網(wǎng)絡由大量微型傳感器設備（節(jié)點）構成。這些節(jié)點分布在特定區(qū)域內(nèi)，能夠周期性的從周圍環(huán)境中收集相關信息，產(chǎn)生并向遠端的基站（Base station，BS）發(fā)送數(shù)據(jù)報?；窘邮铡⒎治霾⒋鎯@些數(shù)據(jù)報，據(jù)此掌握該區(qū)域的相關情況。無線傳感器網(wǎng)絡基于其網(wǎng)絡節(jié)點數(shù)靈活可控、拓撲結構冗余度高等優(yōu)點，在各領域得到了廣泛推廣。微型傳感器節(jié)點的物理尺寸決定了其攜帶電池容量是有限的，而且通常情況下電池能量是無法得到補充的。由于無線傳感器網(wǎng)絡節(jié)點及基站之間傳輸數(shù)據(jù)基本采用的是近距離無線通信方式，因此無線通信方式中節(jié)點收、發(fā)數(shù)據(jù)的能耗是需要重點關注的，其主要影響因素與節(jié)點收發(fā)數(shù)據(jù)的規(guī)則、約定有關，即與網(wǎng)絡協(xié)議密切相關。本文提出了一種基于仿生算法的網(wǎng)絡協(xié)議，對于給定傳感器網(wǎng)絡模型，能使其中節(jié)點以節(jié)能的方式快速有效地將傳感器收集的數(shù)據(jù)傳送到基站處理，從而降低在數(shù)據(jù)傳輸途徑上不必要的能耗。

2網(wǎng)絡協(xié)議細節(jié)

2.1 網(wǎng)絡環(huán)境

本文中對傳感器節(jié)點所部署的網(wǎng)絡環(huán)境進行了如下約定：1）傳感器節(jié)點部署到監(jiān)測區(qū)域時采用飛機或人工隨機投送方式。為了簡化影響條件，約定該區(qū)域為一長寬相等的矩形區(qū)域。所有傳感器節(jié)點的軟硬件配置相同，其配備的電池具有相同的初始電量、具有相同的路由計算能力、數(shù)據(jù)轉發(fā)能力以及有效覆蓋整個檢測區(qū)域范圍的無線通信能力。2）假定傳感器節(jié)點都具備實時監(jiān)測所攜帶電池的剩余電量的能力、都具備無線信號強度檢測能力。3）每個節(jié)點在每個采樣周期產(chǎn)生一條固定長度數(shù)據(jù)報，最終將傳送到在監(jiān)測區(qū)域遠端的固定基站（BS），BS接受、處理、存儲和共享這些數(shù)據(jù)。

2.2 協(xié)議基本思想

由于傳感器節(jié)點電池電量有限且是純消耗性的，電量用完該節(jié)點即宣告失效。當失效節(jié)點達到一定數(shù)量時，整個網(wǎng)絡的數(shù)據(jù)收集能力將大大下降甚至完全失去監(jiān)測作用。因此從降低能耗這一抓手出發(fā)，設計能耗優(yōu)化的網(wǎng)絡工作機制是協(xié)議是否具有實際應用價值的關鍵。對此采取以下措施：1）控制通信范圍，對網(wǎng)絡實行分簇管理，通信僅限于簇內(nèi)節(jié)點之間進行，不同簇節(jié)點相互不進行直接通信。2）簇內(nèi)節(jié)點只與相鄰節(jié)點（一定距離范圍之內(nèi)的節(jié)點）直接通信。采樣數(shù)據(jù)報在相鄰節(jié)點間沿簇內(nèi)路由樹傳遞最終送達簇核心，指令數(shù)據(jù)報沿逆方向傳遞。每個接收節(jié)點當接收并轉發(fā)數(shù)據(jù)報后，會給前一個節(jié)點發(fā)送一反饋報文以保證路由的有效性。3）簇核心由于會比普通節(jié)點消耗更多能量，因此每隔一段時間重新選舉簇核心，以平衡所有節(jié)點的能量消耗。協(xié)議經(jīng)歷分簇、路由形成、正常數(shù)據(jù)傳輸階段組成，具體細節(jié)如下所述：

（1）監(jiān)測區(qū)域劃分為n個簇，在所有節(jié)點中隨機選擇n個節(jié)點作為簇核心。每個節(jié)點擁有一個唯一的整數(shù)ID。在一個采樣周期開始的時候，每個節(jié)點先隨機生成一個范圍在（ID-1）到（ID+1）內(nèi)的隨機數(shù)，然后用此數(shù)mod（ID），得到的值若大于T，則該節(jié)點成為核心節(jié)點，此時其所在的簇ID就是該節(jié)點的ID值。然后該核心節(jié)點發(fā)送群播消息（BDCV），其余節(jié)點收到的群播消息強度如果大于△E1，就選擇加入該簇，△E的大小根據(jù)實際情況選擇。T由公式計算得到：T =[nN?（rmodNn）n]，r為經(jīng)歷的輪數(shù)，N為節(jié)點總數(shù)，n為簇核心的個數(shù)。超過簇的生存期Tc則重新選擇簇核心，這樣既平衡節(jié)點的能量消耗，又防止過于頻繁劃分簇而消耗大量節(jié)點能量。

（2）數(shù)據(jù)傳輸路徑的選擇。為了保存網(wǎng)絡的拓撲信息，每個節(jié)點內(nèi)部會維護一張相鄰節(jié)點信息表。每個節(jié)點接收簇內(nèi)其他節(jié)點發(fā)送的廣播搜索報文BCAB（以恒定功率發(fā)送，含有發(fā)送節(jié)點的ID），如果收到的信號強度大于閾值△E2（由實際情況決定），就將他加入自己的相鄰節(jié)點表中，同時將信號強度Ei也存入對應表格中，因此在獲得相鄰節(jié)點信息的同時，節(jié)點也得到了其相鄰節(jié)點間的鏈路（無線信道）權值，即它們之間的距離信息。接下來需要以簇為單位，計算出簇內(nèi)轉發(fā)路由表。該路由表實質就是對應于簇內(nèi)最短路徑樹，由基于變形蟲算法的計算方法得到。當有節(jié)點失效（發(fā)送節(jié)點接收不到接收節(jié)點的發(fā)送的反饋報文），則該節(jié)點將向全簇節(jié)點發(fā)送廣播消息通告此情況，并激活更新相鄰節(jié)點信息表的進程：簇內(nèi)節(jié)點重新執(zhí)行（2）中操作以重新獲取全局拓撲信息和計算路由。

（3）數(shù)據(jù)采集。節(jié)點在采樣周期內(nèi)將進行若干次的數(shù)據(jù)采集操作，具體次數(shù)由實際情況而定。生成的數(shù)據(jù)報按在每個節(jié)點中存儲的由2.3節(jié)算法計算出來的路由表進行轉發(fā)，直至核心節(jié)點。需要注意的是，并不是每個節(jié)點都會發(fā)起上述的數(shù)據(jù)傳送，而是只能由葉子節(jié)點發(fā)起。路由表中的中間節(jié)點只是在葉子節(jié)點發(fā)起數(shù)據(jù)傳送時，將自己采集得到的數(shù)據(jù)與前一個節(jié)點轉發(fā)來的數(shù)據(jù)進行合并處理，然后再將該數(shù)據(jù)報轉發(fā)出去。因此，每個采樣周期核心節(jié)點只會收到等于葉子節(jié)點總數(shù)的數(shù)據(jù)報，并將這些數(shù)據(jù)報發(fā)送給BS。這樣，可以有效減少數(shù)據(jù)報產(chǎn)生和轉發(fā)的次數(shù)，降低節(jié)點的功耗。

2.3 基于仿生算法的通信路由優(yōu)化

無線信號傳輸距離越遠，數(shù)據(jù)傳輸所需能量消耗越大。為了最大限度降低數(shù)據(jù)傳輸時總的能量消耗，數(shù)據(jù)包應該沿著優(yōu)化過的路由途徑來傳輸。這要求路由算法計算出來的路由由普通節(jié)點到簇核心節(jié)點的跳數(shù)最小，也就是說，簇內(nèi)路由應該是一顆最小路徑樹。由于變形蟲對食物獲取路徑的選擇和傳感器網(wǎng)絡中路由的計算形成具有很高的相似度，同時也由于其算法開銷比較大，因此需要對變形蟲算法改進才能用于路由決策。將變形蟲網(wǎng)絡迷宮對應于傳感器網(wǎng)絡中的一個簇，含有食物源的起點與終點分別對應簇中的核心節(jié)點和普通節(jié)點。網(wǎng)絡中的核心記為C1，普通節(jié)點中的終點記為C2，其他節(jié)點分別表示為Ci（i= 3，4，5...）。連接節(jié)點Ci與節(jié)點Cj的管道可以表示為邊Tij，對應可以表示傳感器網(wǎng)絡中兩節(jié)點間的鏈路，流經(jīng)邊Tij的流量表示為Qij，對應傳感器網(wǎng)絡中的數(shù)據(jù)流量，其滿足泊松定律。在傳感器網(wǎng)絡中，用節(jié)點i處的信號強度用Ei替代壓力pi，因此，公式變?yōu)椋?/p>

3 實驗分析及小結

為驗證協(xié)議效果，將其同PVCHI協(xié)議和文獻[4]中協(xié)議進行對比。實驗考察三種協(xié)議每個采樣周期所有節(jié)點的平均能耗。實驗區(qū)域設定為長寬為50/100/300/500米的矩形區(qū)域內(nèi)，N個節(jié)點隨機分布在該區(qū)域中。PVCHI協(xié)議簇內(nèi)所有節(jié)點一個采樣周期的能耗為：[Ec=（Eeleck+εfskM22πn）（Nn?1）+mp.（k+1）d3bs]，在文獻[4]中總能耗為：[Efc=（Eeleck+εfsM2k（N?1）2）N2+Eeleck（N2?13NN）]，基于仿生算法協(xié)議總能耗為：[Enc=2NEeleck+εfs（k?1）M2?NN（N?n）]。實驗中取數(shù)據(jù)長度為k=2000，n=5。當N=300時，實驗結果見表1。

實驗結果顯示，PVCHI協(xié)議一個采樣周期內(nèi)能耗最多，根本原因之一是每個節(jié)點都會產(chǎn)生和轉發(fā)數(shù)據(jù)報，導致有很大一部分能量用于處理、轉發(fā)冗余數(shù)據(jù)。其次，是由于其路由選擇算法計算得到的路由使傳輸數(shù)據(jù)報時不是最短跳數(shù)。本文提出的改進協(xié)議由于同時減小了數(shù)據(jù)傳輸時的通信距離和數(shù)據(jù)發(fā)收次數(shù)，因而使節(jié)點的能耗降低。無線傳感器網(wǎng)絡的能耗問題是制約和影響其廣泛應用的重要因素之一，實驗證明，本文的解決方案通過平衡節(jié)點功耗，用仿生算法優(yōu)化數(shù)據(jù)傳輸路徑和降低節(jié)點轉發(fā)數(shù)據(jù)的次數(shù)，能有效降低節(jié)點功耗，延長無線傳感器網(wǎng)絡的工作壽命。

參考文獻：

[1] 梁鳴心.基于多頭絨泡菌仿生模型的圖挖掘研究[D].西南大學，2017.

[2] 張曉革.基于多頭絨泡菌的交通網(wǎng)絡設計算法的研究[D].西南大學，2014.

[3] 王慶.基于多頭絨泡菌的路網(wǎng)優(yōu)化算法[D].西南大學，2012.

[4] 陳凌平.一種低功耗自組織傳感器網(wǎng)絡協(xié)議[J].計算機應用研究，2005（2）：209-211.

【通聯(lián)編輯：代影】