一種新的無線傳感網(wǎng)絡(luò)路由算法的仿真設(shè)計與研究

王林林

（中山火炬職業(yè)技術(shù)學(xué)院，廣東中山528436）

一種新的無線傳感網(wǎng)絡(luò)路由算法的仿真設(shè)計與研究

王林林

（中山火炬職業(yè)技術(shù)學(xué)院，廣東中山528436）

本文主要是對關(guān)于網(wǎng)絡(luò)路由算法中的蟻群算法進行研究與分析，并對其仿真數(shù)據(jù)的報文進行研究.首先分析了互聯(lián)網(wǎng)絡(luò)中的無線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸與跳轉(zhuǎn)特性，提出了基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的平面路由協(xié)議中擴散法的路由協(xié)議算法以及層次路由協(xié)議中的LEACH協(xié)議，在分析中發(fā)現(xiàn)這些算法過重依賴于網(wǎng)絡(luò)節(jié)點的功能，在性能方面表現(xiàn)不好.在此基礎(chǔ)上，詳細(xì)闡述了蟻群算法的基本情況、算法原理、實現(xiàn)過程以及在無線傳感網(wǎng)絡(luò)中作為路由協(xié)議基本算法的在執(zhí)行效率上的不足，并提出了添加節(jié)點能量值為影響因素的優(yōu)化算法，最后對基于蟻群算法的路由協(xié)議的無線傳感網(wǎng)絡(luò)的傳輸仿真進行報文設(shè)計，從而實現(xiàn)無線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸.

無線傳感網(wǎng)絡(luò)；蟻群算法；信息素；通信報文

1　引言

隨著科學(xué)技術(shù)的不斷發(fā)展，人們對于生活質(zhì)量和物質(zhì)水平的要求越來越高.互聯(lián)網(wǎng)絡(luò)以其特有的連通性和開放性，已經(jīng)成為人們生活的基礎(chǔ)設(shè)施，成為人們?nèi)粘Ｉ钏璧谋夭豢缮俚囊徊糠?而互聯(lián)網(wǎng)絡(luò)的實現(xiàn)，在網(wǎng)絡(luò)末端是由各個不同類型的網(wǎng)絡(luò)構(gòu)成，通過將不同類型的終端設(shè)備信息連接到互聯(lián)網(wǎng)絡(luò)中，來實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)傳輸與共享.在互聯(lián)網(wǎng)絡(luò)中，無線傳感網(wǎng)絡(luò)是目前較為新型的網(wǎng)絡(luò)，它是集傳感與信息轉(zhuǎn)換技術(shù)、嵌入式技術(shù)以及分布式信息處理技術(shù)與于一體的特有的新型無線網(wǎng)絡(luò)，在民用、軍工、醫(yī)療、科研等各個領(lǐng)域中得到了廣泛的應(yīng)用.對于無線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸與跳轉(zhuǎn)的實現(xiàn)，是需要基于相關(guān)協(xié)議的網(wǎng)絡(luò)軟件和硬件設(shè)施來實現(xiàn)，而這些網(wǎng)絡(luò)軟件和硬件的設(shè)計與實現(xiàn)，則需要遵循專門的路由協(xié)議.網(wǎng)絡(luò)路由協(xié)議本身，規(guī)定了數(shù)據(jù)傳輸?shù)母袷?、方式、傳輸過程以及跳轉(zhuǎn)規(guī)則等，按照專門的網(wǎng)絡(luò)協(xié)議，才能實現(xiàn)無線傳感網(wǎng)絡(luò)數(shù)據(jù)的準(zhǔn)確傳輸與路由跳轉(zhuǎn).所以對于無線傳感網(wǎng)絡(luò)路由算法的研究與仿真設(shè)計，對于了解與學(xué)習(xí)無線傳感網(wǎng)絡(luò)的工作機制與具體實現(xiàn)來說，具有非常重要的現(xiàn)實意義.

2　無線傳感器網(wǎng)絡(luò)的路由協(xié)議

無線傳感網(wǎng)絡(luò)屬于互聯(lián)網(wǎng)絡(luò)的子網(wǎng)絡(luò)，是在互聯(lián)網(wǎng)絡(luò)的末端實現(xiàn)不同類型的網(wǎng)絡(luò)終端設(shè)備的數(shù)據(jù)接入和傳輸?shù)妮^為新型的無線網(wǎng)絡(luò)系統(tǒng).無線傳感網(wǎng)絡(luò)通過嵌入式的信息傳感、采集設(shè)備和數(shù)據(jù)傳輸設(shè)備，將無線傳感網(wǎng)絡(luò)終端設(shè)備的數(shù)據(jù)接入到互聯(lián)網(wǎng)絡(luò)中，與其他服務(wù)器或網(wǎng)絡(luò)設(shè)備進行數(shù)據(jù)傳輸與交換.無線傳感網(wǎng)絡(luò)的主要結(jié)構(gòu)包括了負(fù)責(zé)信息收集的匯聚節(jié)點、信息轉(zhuǎn)換的傳感節(jié)點、信息接收節(jié)點以及數(shù)據(jù)傳輸任務(wù)的管理節(jié)點，通過大范圍隨機的傳感節(jié)點接收數(shù)據(jù)，通過其他接收節(jié)點，最終將數(shù)據(jù)傳送到匯聚節(jié)點，經(jīng)過互聯(lián)網(wǎng)絡(luò)或其他中轉(zhuǎn)設(shè)備可實現(xiàn)數(shù)據(jù)傳輸?shù)阶罱K檢測設(shè)備上.如圖1.所示，為無線傳感網(wǎng)絡(luò)的節(jié)點組成示意圖.

圖1　無線傳感網(wǎng)絡(luò)節(jié)點組成示意圖

在無線傳感網(wǎng)絡(luò)的硬件平臺上，通過網(wǎng)絡(luò)中各個通信協(xié)議，實現(xiàn)數(shù)據(jù)的傳輸與網(wǎng)絡(luò)路由跳轉(zhuǎn).在無線傳感網(wǎng)絡(luò)中，網(wǎng)絡(luò)路由協(xié)議是在不同的應(yīng)用環(huán)境中有所差別的，大體上可以分為兩類路由協(xié)議，分別是以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為分層的平面路由協(xié)議、層次路由協(xié)議等，和以不同的應(yīng)用目的而設(shè)計的QoS路由協(xié)、協(xié)商路由協(xié)議、耦合處理路由協(xié)議等.

在平面路由協(xié)議中，擴散法是常見的較為容易實現(xiàn)的算法.在無線傳感網(wǎng)絡(luò)中，當(dāng)一個節(jié)點向目標(biāo)節(jié)點發(fā)送數(shù)據(jù)時，該節(jié)點會同時向其附近的所有節(jié)點都發(fā)送一份相同的數(shù)據(jù)，這些節(jié)點在接收到該數(shù)據(jù)時，會分析出該數(shù)據(jù)是否為當(dāng)前節(jié)點所需數(shù)據(jù)，如果是，按照同樣的方法，向其附近的其他節(jié)點繼續(xù)擴散，直至到目標(biāo)節(jié)點.如圖2，為屏幕路由協(xié)議的擴散法原理示意圖.

圖2　擴散法原理示意圖

基于擴散法實現(xiàn)的網(wǎng)絡(luò)路由數(shù)據(jù)轉(zhuǎn)換，能夠適應(yīng)不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，健壯性較高，資源浪費少，在無線傳感網(wǎng)絡(luò)中很容易實現(xiàn).

基于層次路由協(xié)議中，LEACH協(xié)議（Low Energy Adaptive Clustering Hierarchy Protocol）是應(yīng)用較為廣泛的網(wǎng)絡(luò)路由協(xié)議.LEACH協(xié)議以簇為單位，將無線傳感網(wǎng)絡(luò)進行均勻劃分，而每個簇內(nèi)部，選擇一個網(wǎng)絡(luò)節(jié)點作為簇頭，該節(jié)點主要負(fù)責(zé)網(wǎng)絡(luò)中的匯聚節(jié)點進行數(shù)據(jù)傳輸，而簇內(nèi)部的其他節(jié)點，則負(fù)責(zé)信息數(shù)據(jù)轉(zhuǎn)換與收集，并將最終數(shù)據(jù)傳送至簇頭節(jié)點.值得說明的是，LEACH協(xié)議對于簇內(nèi)簇頭節(jié)點的選取，并非固定式，而是采用動態(tài)循環(huán)的方式對簇內(nèi)的所有節(jié)點進行選取，這樣一樣，簇頭節(jié)點的信息匯總與發(fā)送的資源消耗則平均地分配到整個簇中，有效地利用了無線傳感網(wǎng)絡(luò)的資源利用率.簇頭節(jié)點的選取的基本過程是首先簇內(nèi)某個節(jié)點在0到1之間隨機選取一個數(shù)值，然后與F(n)進行比較，如果小于該值，則此節(jié)點則為簇頭節(jié)點.F(n)如下表達(dá)式.

其中，x為一個簇內(nèi)某個節(jié)點能夠成為簇頭節(jié)點的可能性，一般以百分比形式顯示，r為循環(huán)的次數(shù)，N為該簇內(nèi)為當(dāng)過簇頭節(jié)點的集合.使用LEACH協(xié)議進行無線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸時，首先確定簇，然后選定簇頭節(jié)點，然后對各個簇頭節(jié)點與基本網(wǎng)絡(luò)建立傳輸調(diào)度與傳輸機制，最終實現(xiàn)各個無線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸.如圖3，是LEACH協(xié)議構(gòu)建的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖.

圖3　基于LEACH協(xié)議的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖

3　蟻群算法的路由協(xié)議

3.1蟻群算法簡介

在無線傳感網(wǎng)絡(luò)實現(xiàn)的路由協(xié)議較多，功能也都較為齊全，但是就整個無線網(wǎng)絡(luò)的能量消耗、服務(wù)質(zhì)量、可靠性、魯棒性等各個方面綜合考慮，基于仿生學(xué)原理的蟻群算法則能夠很好地在實現(xiàn)無線傳感網(wǎng)絡(luò)數(shù)據(jù)傳輸與跳轉(zhuǎn)的前提下，將網(wǎng)絡(luò)能量耗損、網(wǎng)絡(luò)數(shù)據(jù)質(zhì)量、魯棒性等各個方面達(dá)到很好的標(biāo)準(zhǔn).

蟻群算法是典型的仿生學(xué)算法，主要是仿照螞蟻在覓食過程中尋找最短路徑的思路來實現(xiàn)的算法.螞蟻在覓得食物后，會返回到蟻巢中通知其他螞蟻一起來搬運食物，而這只螞蟻在返回到蟻巢過程中，會在路上釋放信息素，以確定其他螞蟻在出來覓食時能正確找到食物源.假如從食物到蟻穴之間，并非一條直線路程，而是有多條路徑，那么初次時，可能會有不同的螞蟻從不同的路徑出發(fā)，而在眾多的路徑中，肯定存在一條最優(yōu)的路徑，能夠讓螞蟻以最短的時間折返，而折返過程中，它們就會留下信息素，此時，其他路徑的螞蟻并會返回到蟻穴.而后續(xù)的螞蟻，則會優(yōu)先選擇有信息素的路徑去搬運食物，而如此過往之后，在最后路徑上留下的信息素最多，而這條路徑也就是食物與蟻穴之間的最優(yōu)路徑.從上述螞蟻覓食的過程中可以發(fā)現(xiàn)，最優(yōu)路徑的選擇是由路徑上的信息素來決定，信息素越多，后續(xù)的螞蟻選擇這條路徑的概率就越大，而折返之間則又釋放更多的信息素.

蟻群算法在無線傳感網(wǎng)絡(luò)中的應(yīng)用無論是從技術(shù)上還是從基本原理上是非常適合的，首先，蟻群算法是采用仿生學(xué)算法，螞蟻本身沒有思維，所有的動作全都來自于本能，而蟻群算法的基本理念就是采用螞蟻本能的行為，與無線傳感網(wǎng)絡(luò)中的數(shù)據(jù)傳輸方式非常相似，采用蟻群算法最終使得無線傳感網(wǎng)絡(luò)中的數(shù)據(jù)自組織、自適應(yīng)，并且能夠根據(jù)不同的網(wǎng)絡(luò)環(huán)境動態(tài)地尋找到最優(yōu)的傳輸路徑，大大降低了控制平臺的應(yīng)用，降低了無線傳感網(wǎng)絡(luò)的設(shè)計實施和維護成本.其次，由于基于蟻群算法的無線傳感網(wǎng)絡(luò)節(jié)點與傳輸路徑，都是動態(tài)的、實時的，所以對于當(dāng)前無線傳感網(wǎng)絡(luò)來說，傳輸數(shù)據(jù)的方式具有實時性，即方式永遠(yuǎn)是最優(yōu)的.同時，對于無線傳感網(wǎng)絡(luò)中單一節(jié)點來說，計算與存儲、能量供給等各個資源非常有限，蟻群算法使無線傳感網(wǎng)絡(luò)的節(jié)點突破了單一性，拋棄了單一節(jié)點的限制，每個節(jié)點只需要按照既定的簡單的規(guī)則實現(xiàn)相應(yīng)的功能，彼此之間相互協(xié)作最終形成了一個完整的整體，無論從計算能力、傳輸時間還是從能量耗損來說，都使無線傳感網(wǎng)絡(luò)實現(xiàn)質(zhì)的飛躍.再者，基于蟻群算法路由協(xié)議的無線傳感網(wǎng)絡(luò)，每個節(jié)點包含了與之關(guān)聯(lián)的所有路徑的信息素濃度值，實際運行時，該節(jié)點的每條路徑都有可能被通過，從整體來看，無線傳感網(wǎng)絡(luò)的連通路徑是非常多樣的.最后，蟻群算法路由協(xié)議使得整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)能夠靈活動態(tài)調(diào)整，無論是節(jié)點添加或更換，還是節(jié)點或路徑破壞失效，在蟻群算法的路由協(xié)議中，這些都不會改變整體結(jié)構(gòu)，通過信息素值的設(shè)定，網(wǎng)絡(luò)是不會受外界環(huán)境變換而影響正常工作的.

3.2蟻群算法建模

蟻群算法就是以螞蟻覓食尋找最優(yōu)路徑的方法來設(shè)計整個計算過程.以旅行商問題為例，假如一共有n個城市，要求選擇出從一個城市出發(fā)，對其他城市都要經(jīng)過一次，最后能夠回到出發(fā)城市的最短的路徑.假設(shè)有m個螞蟻，在初始化時，各個城市之間的路徑上信息素的濃度值都為零.那么在某個時刻t，螞蟻a從城市x到城市y移動的概率為：

在上式中，Paxy為螞蟻a從x城市移動到y(tǒng)城市的概率.α與β分別為路徑的信息素與路徑啟發(fā)因子，二者會對螞蟻a的路徑選擇做出影響，G則代表螞蟻a為經(jīng)過的城市.假如x，y城市距離為d，則ηxy=

隨著時間的推移，在螞蟻a走完了所有的城市之后，路徑上的信息素會不斷揮發(fā)，假設(shè)其揮發(fā)參數(shù)為z，那么在經(jīng)過n時刻后，路徑上的信息素就會不斷揮發(fā)，則信息素影響的參數(shù)將會動態(tài)變化，變化公式如下：

3.3蟻群算法流程

按照蟻群算法的基本原理，以及蟻群算法的仿生學(xué)過程，蟻群算法的基本流程就是按照螞蟻覓食過程的來設(shè)計.其大致過程包括三個步驟，第一就是初始化整個蟻群數(shù)據(jù)以及路徑信息素數(shù)據(jù)，第二階段就是設(shè)置路徑上信息素添加與揮發(fā)的規(guī)則，即螞蟻走過路徑之后的信息素添加的規(guī)則算法以及信息素的揮發(fā)算法，第三階段設(shè)定螞蟻的判斷路徑和添加信息素，即螞蟻根據(jù)路徑信息素濃度判斷路徑以及走過路徑后增加信息素值的算法.其具體的流程如下：

（1）初始化所有參數(shù)變量，設(shè)定路徑信息素值為零，設(shè)定螞蟻留下信息素和信息素?fù)]發(fā)的參數(shù)與τxy

（2）隨機分配螞蟻總數(shù)，使其在所有城市內(nèi)

（3）記錄當(dāng)前所有螞蟻的所有位置信息

（4）計算每個螞蟻的狀態(tài)移動概率，選擇概率最大值的城市最為下一個移動目標(biāo)城市

（5）匯總所有螞蟻的最優(yōu)解，整合數(shù)據(jù)，記錄最優(yōu)解

（6）按照信息素值變化規(guī)則修改路徑信息素值

（7）判斷是否滿足結(jié)束條件，如果是，輸出當(dāng)前最優(yōu)解，如果否則跳至第三步

如圖4所示，為蟻群算法的基本流程

圖4　蟻群算法流程

3.4蟻群算法的優(yōu)化

在蟻群算法實現(xiàn)路由協(xié)議，應(yīng)用到無線傳感網(wǎng)絡(luò)之后，會通過信息素值的不斷積累和動態(tài)更新，很容易找到網(wǎng)絡(luò)傳輸?shù)淖顑?yōu)路徑，但是在性能方面卻有所不足，例如，蟻群算法執(zhí)行時間較長，而且很難進行更深層次的搜索，尤其是在節(jié)點能量變化之后，對算法的執(zhí)行效率更是影響較大，所以在最初的蟻群算法上，需要進行改進.

首先是選擇下個節(jié)點的概率計算，改進的計算公式如下：

在上述公式中，E0為無線傳感網(wǎng)絡(luò)節(jié)點的初始電量值，Exy表示該無線傳感網(wǎng)絡(luò)節(jié)點當(dāng)前可用電量值，θ1與θ2表示兩個加權(quán)值，分別為路徑距離以及節(jié)點當(dāng)前可用電量的影響比例，二者和為1.這樣一樣，螞蟻在選擇下一個目標(biāo)節(jié)點時，需要考慮的因素就要添加上路徑距離以及節(jié)點的可用電量.

4　基于蟻群算法的路由協(xié)議仿真的報文設(shè)計

基于蟻群算法實現(xiàn)的無線傳感網(wǎng)絡(luò)路由協(xié)議的仿真，完全是按照蟻群算法的基本定義變量以及實現(xiàn)流程，來設(shè)計相應(yīng)的數(shù)據(jù)和流程，在一定的平臺上進行實現(xiàn).

基于蟻群算法的描述和改進后蟻群算法的概率計算公式，在一個無線傳感網(wǎng)絡(luò)的路由協(xié)議仿真中，需要有以下幾個變量，存儲網(wǎng)絡(luò)節(jié)點的信息表和變量，存儲走過路徑長度（經(jīng)過節(jié)點個數(shù)）的變量，節(jié)點電量的原始值與當(dāng)前值的變量，記錄路徑的信息素濃度值的變量，螞蟻信息表和變量，單個螞蟻所處的節(jié)點變量以及下一個目標(biāo)節(jié)點的變量，為了方便使用與計算，將無線傳感網(wǎng)絡(luò)的節(jié)點屬性值設(shè)定節(jié)點信息表，包含節(jié)點ID值，當(dāng)前節(jié)點到匯聚節(jié)點的節(jié)點個數(shù)，當(dāng)前節(jié)點電量值；相鄰節(jié)點信息表，包含相鄰節(jié)點ID，二者之間路徑的信息素濃度值，以及相鄰節(jié)點的可用電量值；螞蟻信息表，包含螞蟻ID值，當(dāng)前所處節(jié)點ID以及目標(biāo)節(jié)點ID.

其次，為了能夠是整個無線傳感網(wǎng)絡(luò)實現(xiàn)蟻群算法的基本功能，需要通過發(fā)送數(shù)據(jù)報文來模擬螞蟻覓食的行為，那么在網(wǎng)絡(luò)路由協(xié)議模擬仿真時，需要設(shè)計專門的各種報文來實現(xiàn)相應(yīng)的操作.如螞蟻覓食報文，節(jié)點向匯聚節(jié)點反饋數(shù)據(jù)報文，能量節(jié)點報文等.首先，螞蟻覓食報文是最主要的報文形式，也是基于蟻群算法實現(xiàn)的網(wǎng)絡(luò)路由協(xié)議的無線傳感網(wǎng)絡(luò)中傳輸數(shù)據(jù)相對較多的數(shù)據(jù)格式之一.那么在設(shè)計螞蟻數(shù)據(jù)報文時，首先有專門的字段表示該報文類型，然后還有其他字段信息表示當(dāng)前報文經(jīng)過的節(jié)點數(shù)，以及源節(jié)點地址信息與目標(biāo)節(jié)點地址信息，從而形成一個完整的數(shù)據(jù)報文格式.反饋數(shù)據(jù)報文的設(shè)計，同樣首先需要有字段保存報文類型信息，然后有專門的字段包含想?yún)R聚節(jié)點發(fā)送信息的源節(jié)點信息，最后包含數(shù)據(jù)信息以及相關(guān)的控制、校驗等控制配置信息，從而形成為完整的數(shù)據(jù)報文.能量報文是更新相鄰節(jié)點電量值的報文數(shù)據(jù)，首先需要專門的字段包含報文類型，然后是包含報告電量信息的節(jié)點ID值以及當(dāng)前可用的有效電量值的數(shù)據(jù)信息，從而形成完整的能量報文.通過設(shè)計的相應(yīng)報文信息，按照蟻群算法的基本流程，就可以對蟻群算法的路由協(xié)議進行仿真.

5　總結(jié)

蟻群算法實現(xiàn)的無線傳感網(wǎng)絡(luò)路由協(xié)議，主要是依靠仿生學(xué)的螞蟻覓食的基本原理來實現(xiàn)，通過設(shè)計專門的數(shù)學(xué)模型，來詳細(xì)分析其基本的工作原理，通過對改進后的蟻群算法的仿真，可以學(xué)習(xí)到無線傳感網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)幕緳C制，對于學(xué)習(xí)研究無線傳感網(wǎng)絡(luò)以及路由協(xié)議設(shè)計，進而提升和優(yōu)化路由算法，都是非常有幫助的.

〔1〕郭彥芳.基于蟻群算法的典型路由協(xié)議的比較研究[J].無線電通信技術(shù)，2015(04).

〔2〕沈琳.基于遺傳蟻群算法的QoS多播路由算法在AdHoc網(wǎng)絡(luò)中運用方法的研究[J].電子技術(shù)與軟件工程，2015(13).

〔3〕李鋒.改進蟻群算法在WSN路由優(yōu)化中的應(yīng)用[J].微處理機，2015(04).

〔4〕孟建東.基于改進蟻群算法的計算機網(wǎng)絡(luò)路由優(yōu)化研究[J].數(shù)字技術(shù)與應(yīng)用，2015(08).

〔5〕楊婷，白云麗，姜新華.基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)路由[J].內(nèi)蒙古大學(xué)學(xué)報(自然科學(xué)版)，2015(01).

〔6〕鄭波，崔寶同.基于混沌粒子群與蟻群算法的WSN路由協(xié)議[J].電子設(shè)計工程，2015(01).

〔7〕S.Nakrani,C.Tovey.On honey bees and dynamic server allocation in internet hosting centers. AdaptiveBehavior-Animals,Animats,Software Agents,Robots,Adaptive Systems.2004.

〔8〕MichelGendreau,Fran?oisGuertin,Jean-Yves Potvin,RenéSéguin.Neighborhoodsearch heuristicsforadynamicvehicledispatching problemwithpick-upsanddeliveries[J]. Transportation Research Part C.2006(3).

〔9〕李靖平.基于802.11MAC協(xié)議的無線傳感器數(shù)據(jù)流優(yōu)先級模型.通化師范學(xué)院學(xué)報,2014(6):15.

TP212；TP393

A

1673-260X（2016）03-0032-04

2015-12-30