高 靜，朱永利，李麗芬

（華北電力大學(xué)控制與計算機工程學(xué)院，河北保定 071003）

基于蟻群算法的長鏈狀無線傳感網(wǎng)絡(luò)路由算法

高 靜，朱永利，李麗芬

（華北電力大學(xué)控制與計算機工程學(xué)院，河北保定 071003）

針對輸電線路監(jiān)測系統(tǒng)對無線傳感器網(wǎng)絡(luò)實時性和可靠性要求較高的特點，提出了一種用于線路監(jiān)測傳感網(wǎng)絡(luò)的帶信息素負增長的蟻群算法。該算法中不需要網(wǎng)絡(luò)節(jié)點維護全局信息，但需要賦予唯一的編號。啟發(fā)函數(shù)計及了鏈路的時延、收包率和距離匯聚節(jié)點的跳數(shù)，并經(jīng)過試驗增加了以參數(shù)α的不同選取可以調(diào)整跳數(shù)在整個選擇過程中所占的重要程度。算法還為當前不可行和擁塞節(jié)點設(shè)置定時器，超時后可重新參與路由選擇。仿真結(jié)果表明，相比基本蟻群算法，該算法能夠找到具有更好性能的路由。

長鏈狀無線傳感器網(wǎng)絡(luò)；輸電線路監(jiān)測；蟻群算法；路由

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由一組傳感器節(jié)點通過無線介質(zhì)連接構(gòu)成的無線網(wǎng)絡(luò)，它采用Ad Hoc方式配置大量微型的智能傳感節(jié)點，通過節(jié)點的協(xié)同工作來采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中的目標信息［1，3］，它可被部署在各種非布線區(qū)、電源供給困難和人員不易到達的區(qū)域?；跓o線傳感器網(wǎng)絡(luò)的輸電線路在線監(jiān)測技術(shù)是一門多學(xué)科高度交叉、知識高度集成的新興技術(shù)［2］，其網(wǎng)絡(luò)的拓撲結(jié)構(gòu)一般為長鏈輻射狀，這種傳感器網(wǎng)絡(luò)多具有集中式數(shù)據(jù)接收、多跳傳輸、多對一流量模式等特征。

目前人們對于這種長鏈狀無線傳感網(wǎng)絡(luò)的研究比較少，對于長鏈狀輸電線路監(jiān)測用無線傳感網(wǎng)絡(luò)的研究就更少，文獻［7］中提出的路由算法是基于固定簇頭的分層路由，采用匯聚節(jié)點查詢的方式，簇頭對簇內(nèi)的節(jié)點數(shù)據(jù)進行整合并轉(zhuǎn)發(fā)，但并不適合事件驅(qū)動的實時應(yīng)用。PAGASIS（Power－EfficientGathering in Sensor Information Systems）［6］協(xié)議是一種典型的基于鏈狀結(jié)構(gòu)的路由協(xié)議，該算法的核心思想是利用貪婪算法生成一條由所有節(jié)點組成的單鏈，鏈上的節(jié)點只與自己的鄰居節(jié)點通信。該協(xié)議追求的目標是節(jié)點能耗的均衡和網(wǎng)絡(luò)壽命的延長，但是當節(jié)點鏈過長時，數(shù)據(jù)傳輸時延將會急劇增長，不適合實時應(yīng)用。因此，雖然結(jié)構(gòu)和本系統(tǒng)有相似之處，但是卻不滿足本系統(tǒng)的性能要求。文獻［8］提出一種基于云模型的多蟻群路由優(yōu)化算法，利用多規(guī)則云發(fā)生器來調(diào)整信息素殘留系數(shù)，利用多蟻群來同時找到多條路徑；文獻［11］提出一種將蟻群算法與遺傳算法結(jié)合的路由優(yōu)化算法，提高了最優(yōu)解的質(zhì)量，但算法對于性能較弱的傳感器節(jié)點來說稍顯復(fù)雜。

文獻［5］提出一種信息素負反饋的機制，通過在較好的路徑上留下正信息素，在較差的路徑上留下負信息素，從而提高了算法的性能和效率。筆者在以上算法的基礎(chǔ)上，提出一種用于線路監(jiān)測傳感網(wǎng)絡(luò)的帶信息素負增長的蟻群算法，算法為每個節(jié)點設(shè)置編號，用于指引螞蟻的行動，從而避免環(huán)路的產(chǎn)生。仿真實驗結(jié)果證明了算法具有較好的路由性能。

1 輸電線路監(jiān)測傳感網(wǎng)絡(luò)簡介

1.1 輸電線路監(jiān)測系統(tǒng)的網(wǎng)絡(luò)模型

架空輸電線路的距離長，中途有眾多的掛有絕緣子的桿塔，每個桿塔的每相上設(shè)置一個傳感節(jié)點，在每組輸電線上設(shè)置一個匯聚節(jié)點，用于收集該站各條出線的所有傳感節(jié)點的數(shù)據(jù)，并與線路監(jiān)控中心服務(wù)器相連，用于保存各絕緣子泄漏電流的歷史數(shù)據(jù)。抽象出的無線傳感器網(wǎng)絡(luò)模型如圖1所示。三個節(jié)點為一組，表示線路的三相，節(jié)點采集到的數(shù)據(jù)通過無線鏈路進行多跳傳輸，采用全向天線，通信范圍能達到2－3跳。

1.2 基于輸電線路監(jiān)測的無線傳感器網(wǎng)絡(luò)特點

基于輸電線路監(jiān)測的無線傳感器網(wǎng)絡(luò)具有如下幾個特點：（1）節(jié)點部署相對規(guī)則，部署后不再移動；（2）區(qū)域節(jié)點密度比較小，相鄰桿塔相距幾十米到幾百米，有的甚至上千米；（3）節(jié)點能量不受限，通過在輸電線路上套裝可開口的特制互感器，并在二次側(cè)對感應(yīng)電流進行整流、穩(wěn)壓即可取得電源；（4）節(jié)點定位、時間同步可通過安裝GPS來解決；（5）數(shù)據(jù)傳輸對實時性、可靠性有較高的要求；（6）匯聚節(jié)點及其附近節(jié)點除了要傳輸自身的數(shù)據(jù)還需轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)，任務(wù)量比較重，較易出現(xiàn)網(wǎng)絡(luò)擁塞現(xiàn)象。

1.3 節(jié)點編號

節(jié)點的輻射狀規(guī)則部署給節(jié)點的編號帶來了方便。本文采用給節(jié)點進行編號的方式來表明節(jié)點離匯聚節(jié)點的遠近，從而在路由建立過程中對節(jié)點的選擇提供參考。由于本文只對一段線路進行研究，故編號采用兩段的方式，匯聚節(jié)點編號為0－0，離匯聚節(jié)點最遠的一層節(jié)點由上到下依次編號為1－1，1－2，1－3，次遠層的節(jié)點編號為2－1，2－2，2－3。編號的前一段表示離匯聚節(jié)點的遠近，編號越大，離匯聚節(jié)點越近，編號的后一段表示同層節(jié)點的位置關(guān)系。

圖1 輸電線路監(jiān)測系統(tǒng)的無線傳感器網(wǎng)絡(luò)模型

2 線路監(jiān)測傳感網(wǎng)絡(luò)的帶信息素負反饋路由算法的提出

像螞蟻這類群居昆蟲，雖然沒有視覺，卻能找到由蟻穴到食物源的最短路徑。人們經(jīng)過大量的研究發(fā)現(xiàn)，螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素（pheromone）的物質(zhì)，螞蟻傾向于朝著該物質(zhì)強度高的方向移動，于是表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率越大。通過這種正反饋性，螞蟻依據(jù)轉(zhuǎn)移概率由位置i轉(zhuǎn)移到位置j，算法通過多次迭代收斂到最優(yōu)結(jié)果［4］，蟻群算法已經(jīng)被用于求解計算機網(wǎng)絡(luò)中的QOS路由［10，11］等問題。

文獻［5］提出了一種信息素負反饋的機制，按照解的好壞對蟻群進行排序，設(shè)置一個比例參數(shù)φ∈（0，1］，排名前m×φ的螞蟻將有權(quán)在其經(jīng)過的路徑上留下正信息素，此信息素有吸引同伴的作用，排名在m×φ之后的螞蟻在其經(jīng)過的路徑上留下負信息素，此信息素將警告同伴不要走這條路徑。

2.1 路由建立過程

2.1.1 準備工作

（a）借助GPS定位系統(tǒng)獲得節(jié)點的地理位置信息并對節(jié)點進行統(tǒng)一編號，設(shè)節(jié)點的編號為n1－n2；

（b）通過HELL0包周期性向鄰居節(jié)點廣播自己的信息。在HELL0包中除了包含節(jié)點的坐標位置信息以外，還包括時間戳，這樣每個節(jié)點都會獲得相鄰節(jié)點的地理位置信息，并從收發(fā)節(jié)點的時間差中減去接收節(jié)點的處理時間，就可以獲得鄰節(jié)點的通信延時，來表示網(wǎng)絡(luò)的負載情況，設(shè)通信延時為delay；

（c）計算鏈路收包率（packet reception rate，PRR），PRR＝Lr／Ls，Lr為成功接收到的數(shù)據(jù)包個數(shù)，Ls為鏈路發(fā)送的總數(shù)據(jù)包數(shù)。

（d）設(shè)置公告板，用于記錄每個源節(jié)點到sink節(jié)點的最優(yōu)路徑，初始化為空；

（e）集合DE（Died End）用于放置不可行和擁塞的節(jié)點，初始化為空，當節(jié)點負載過重時，向子節(jié)點發(fā)送反向壓力信標，并將自己放在集合DE中，集合中每個節(jié)點設(shè)置一個定時器，超時即被解禁，從本集合中移除，重新成為活躍節(jié)點，參與數(shù)據(jù)的轉(zhuǎn)發(fā)。

每個節(jié)點維護一張鄰節(jié)點情況表，用于記錄鄰節(jié)點的編號、延時和鏈路收包率。

設(shè)置延時和鏈路質(zhì)量的約束條件：

2.1.2 建立過程

（a）初始化網(wǎng)絡(luò)中每一條邊的信息素為1；在每一次迭代中，網(wǎng)絡(luò)中的每一個結(jié)點s都有Ant＿Count只目的節(jié)點為sink的正向螞蟻Fs－＞sink出發(fā)，它的任務(wù)是找到一條通往sink節(jié)點的高性能的可行路徑；正向螞蟻與逆向螞蟻采用比數(shù)據(jù)分組更高優(yōu)先級的鏈路隊列，從而加快路徑建立的速度；

（b）在每個節(jié)點i上，集合NC為節(jié)點i的所有鄰節(jié)點集合中滿足約束條件（1）和（2）的節(jié)點集合，將不屬于DE集合并且節(jié)點的n1編號大于i的n1編號的節(jié)點，即相對比節(jié)點i離sink節(jié)點更近的鄰節(jié)點放入集合NC1中。

（1）如果｜NC1｜＞0，則螞蟻依據(jù)轉(zhuǎn)移概率在鄰節(jié)點中選擇下一個要遍歷的節(jié)點，選擇相鄰節(jié)點j作為下一個遍歷結(jié)點的轉(zhuǎn)移概率Pij定義如下：

啟發(fā)式函數(shù)綜合考慮了鏈路質(zhì)量、節(jié)點對之間的時延和距離匯聚節(jié)點的跳數(shù)，以期選擇出滿足實時性和可靠性要求的路徑。

（2）如果｜NC1｜＝0，即不存在比節(jié)點i離sink節(jié)點更近的節(jié)點，則螞蟻回退一步，并將節(jié)點i放入集合DE中；

（3）到達sink結(jié)點后，前向螞蟻Fs－＞sink將生成另一個逆向螞蟻Bsink－＞s，它把自己的所有記憶轉(zhuǎn)移給逆向螞蟻，而自身將被刪除。如果在到達目的結(jié)點前，正向螞蟻的生存時間超過了最大生存時間max＿life，那么這個螞蟻將被刪除。逆向螞蟻行進的路徑與它對應(yīng)的正向螞蟻完全相同，但是行進的方向卻正好相反，負責信息素的更新，其更新規(guī)則如下：

從以上公式可以看出：所選路徑的總延時越小，包成功率越高，則相應(yīng)路徑的信息素增長越多，即信息素的增長與路徑的質(zhì)量成正比。

（4）更新公告板，如果當前求出的最優(yōu)路徑比公告板上記錄的更優(yōu)秀，則將其替換為本次求出的路徑。

（5）達到最大迭代次數(shù)時算法結(jié)束。

2.2 數(shù)據(jù)傳輸過程

數(shù)據(jù)依據(jù)2.1節(jié)找到的最優(yōu)路徑進行傳送，當節(jié)點的轉(zhuǎn)發(fā)隊列過長時，為保證轉(zhuǎn)發(fā)的實時性，該節(jié)點發(fā)出警告信息alert，該alert消息記錄了該節(jié)點的節(jié)點編號n1－n2，并通過洪泛將該消息通知給其它節(jié)點，之后放入集合DE中。當源節(jié)點接收到該alert消息時，判斷該節(jié)點編號n1－n2是否在自己的路徑列表中，如果在則n1－n2的上一跳節(jié)點根據(jù)2.1節(jié)路由算法重新尋找除n1－n2以外的新的下一跳節(jié)點。

3 算法分析及仿真結(jié)果

3.1 算法分析

本文算法為分布式的算法，螞蟻從各個源節(jié)點出發(fā)并行工作查找到sink節(jié)點的最優(yōu)路徑，算法同時考慮了信息素濃度、節(jié)點間延時、鏈路的質(zhì)量和節(jié)點距離sink節(jié)點的跳數(shù)。由公式（2）可以看出，鏈路的收包率越高，節(jié)點之間的延時越小，距離匯聚節(jié)點越近，則選擇概率越大，從而可以很好地保證可靠性和實時性，并能盡量快速地、少跳數(shù)地形成到達匯聚節(jié)點的路由。算法引入負反饋機制，提高了解的質(zhì)量，但卻因為要排序比較而增加了算法的計算量，因排序而增加的比較次數(shù)為：n（n－fix（n＊φ）），復(fù)雜度為O（n）。另外，算法通過對每個節(jié)點進行編號，有效地避免了環(huán)路的產(chǎn)生。

3.2 仿真實驗

本文用仿真軟件MATLAB 7.1作為仿真平臺，仿真實驗時采用如圖1所示的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖，其中鏈路的時延、包成功接收率的值由系統(tǒng)隨機產(chǎn)生，時延在1～10ms，包成功接收率在0.85～1之間，其中D＝9.5ms，R＝0.9。依據(jù)文獻［5］的參數(shù)選擇，α＝1，β＝4.5，ρ＝0.2，Q＝0.1，φ＝0.9，r表示節(jié)點的通信半徑（單位為跳數(shù)），m表示本長鏈的節(jié)點層數(shù)。

圖2和圖3是在網(wǎng)絡(luò)層數(shù)為100，節(jié)點的通信半徑為3跳的情況下進行的，其中性能的評價依據(jù)公式（8）計算。從圖中可以看出，當α＝0時，所選出的最優(yōu)路徑性能值最小，路徑總跳數(shù)最多。這是因為啟發(fā)函數(shù)中并沒有考慮到跳數(shù)這個參數(shù)，所以盡管所選路徑的單跳時延和鏈路包成功率最優(yōu)，但因總路徑的跳數(shù)更多，從而影響總路徑的性能；當α＝1／r時，所選出的最優(yōu)路徑性能值最大，總跳數(shù)最少；而當α＝1／（r＊r）時，所選出的最優(yōu)路徑性能值和總跳數(shù)居中。原因就在于跳數(shù)在α＝1／r中所占得比重更大，但是過分增大α的值將會導(dǎo)致跳數(shù)掩蓋掉其他兩個參數(shù)。由圖3看出，當α＝1／r時所選路徑的總跳數(shù)在37到50之間，并沒有導(dǎo)致參數(shù)跳數(shù)覆蓋掉其他兩個參數(shù)，所以本論文中取α＝1／r。

圖2 不同α取值下最優(yōu)路徑性能變化情況

圖3 不同α取值下所選路徑總跳數(shù)的變化情況

圖4 兩算法最優(yōu)路徑性能變化情況

圖4是在網(wǎng)絡(luò)層數(shù)為100，節(jié)點的通信半徑為2跳，迭代次數(shù)t為400，每個源節(jié)點的螞蟻數(shù)量為6的情況下進行的，其中性能的評價依據(jù)公式（8）計算。從圖2中可以看出，相比基本蟻群（Base Ant Algorithm，BAA）算法，帶信息素負增長的蟻群算法（Base Ant Algorithm With Negative pheromone growth，BAWN）能找出性能更優(yōu)秀的路徑，這與文獻［5］中的結(jié)論也是相一致的。

由圖5可以看出，增加在每個源節(jié)點放置螞蟻的數(shù)量，能夠加快獲得最優(yōu)解的速度，但是隨著迭代的進行，這種優(yōu)勢越來越弱。增加螞蟻的數(shù)量會增加因排序而進行的比較次數(shù)，所以應(yīng)該根據(jù)傳感器節(jié)點的能力來選擇合適的螞蟻數(shù)量。

圖5 源節(jié)點放置不同螞蟻數(shù)量下最優(yōu)路徑性能變化情況

4 結(jié)論

本文以輸電線路監(jiān)測為應(yīng)用背景，針對系統(tǒng)對無線傳感器網(wǎng)絡(luò)實時性和可靠性要求較高的特點，提出了一種用于線路監(jiān)測傳感網(wǎng)絡(luò)的帶信息素負增長的蟻群算法，通過對每個節(jié)點進行編號，有效地避免了環(huán)路。在算法中，距離匯聚節(jié)點越近，延時越小，可靠性越高的節(jié)點被選擇的可能性越大，反向壓力信標用來緩解某個節(jié)點任務(wù)過重的情況，從而預(yù)防擁塞的發(fā)生，定時器的設(shè)定可以使優(yōu)秀節(jié)點在經(jīng)過一個時間段的休眠后重新成為活躍節(jié)點，這也是對網(wǎng)絡(luò)整體性能的一個考慮。對于啟發(fā)函數(shù)中的參數(shù)α，本文是通過實驗選取的，當α＝1／r時，相比較α＝0和α＝1／（r＊r）時在所選路徑的性能上更優(yōu)秀，但本文并沒有給出α的最優(yōu)表現(xiàn)形式。仿真實驗表明，帶信息素負增長的蟻群算法能夠獲得更高質(zhì)量的解，因此該算法相比基本蟻群算法更適合于長鏈狀無線傳感器網(wǎng)絡(luò)。

［1］Tilakk S，ABU－Ghazaleh NB，Heinzelman W.A Taxonomy of wireless micro sensor network models［J］.Mobile Computing and Communications Review，2002，1（2）：1－8.

［2］黃新波.絕緣子泄漏電流在線監(jiān)測系統(tǒng)的設(shè)計與應(yīng)用［J］.電測與儀表，2007，44（4）：9－14.

［3］孫利民，李建中，陳渝等.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社.2005.

［4］Marco Dorigo，Thomas Stutzle著，張軍，胡曉敏，羅旭耀等譯.蟻群優(yōu)化［M］.北京：清華大學(xué)出版社.2007.

［5］馮春時.群智能優(yōu)化算法及其應(yīng)用［D］.中國科學(xué)技術(shù)大學(xué)，2009.

［6］余勇昌，韋崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法［J］.電子學(xué)報，2008，36（7）：1309－1313.

［7］王陽光，尹項根，游大海等.基于無線傳感器網(wǎng)絡(luò)的電力設(shè)施冰災(zāi)實時監(jiān)測與報警系統(tǒng)［J］.電網(wǎng)技術(shù)，2009，33（7）：14－19.

［8］李麗芬，朱永利，張君艷.基于隸屬云蟻群算法的長鏈形無線傳感器網(wǎng)絡(luò)路由優(yōu)化［J］.計算機工程與科學(xué).2010，32（11）：10－14.

［9］Kumar R，Wolenetz M，Agarwalla B，Shin J，Hutto P，Paul A，Ramachandran U.DFuse.A framework for distributed data fusion［C］.In：Proc1st ACM Conf on Embedded Networked Sensor Systems（SenSys’03），Los Angeles，CA.November，2003.114－125.

［10］Zhang Su－bing，Liu Ze－min.A QoS routing algorithm based on ant algorithm［C］.In：IEEE International Conference on Communications，2001，5：1581－1585.

［11］張君艷，朱永利，彭偉.大規(guī)模帶狀無線傳感器網(wǎng)絡(luò)QoS路由優(yōu)化的研究［J］.電力科學(xué)與工程，2010，26（4）：11－15.

The algorithm based on an ant colony algorithm for wireless sensor networks with long－chain structure

GAO Jing，ZHU Yong－li，LI Li－fen

（SchoolofControl＆ComputerEngineering，NorthChinaElectricPowerUniversity，BaodingHebei071003，China）

With the high demand of real－time and reliability of monitoring system of power transmission lines，an ant colony algorithm with negative information growth is presented.Each node is no need to maintain the global information，but the only number must be given.The timer is set for the current not feasible and congestion nodes.nodes can participate in routing when the timer is overtime.The simulation results show that the proposed algorithm can obtain better performance than basic Ant Colony algorithm.

Long－chain of wireless sensor network；Transmission line monitoring system；Ant colony algorithm；Routing

TP301

：A

1001－9383（2011）03－0019－06

2011－06－30

國家自然科學(xué)基金資助項目（60974125）

高 靜（1985－），女，河北廊坊人，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò).