基于蟻群的無線電源管理網(wǎng)絡路由算法

姜福祥，錢建波，于正永

(淮安信息職業(yè)技術學院，江蘇淮安223005)

0 引言

目前人們正致力于利用檢測傳感器實時檢測電源運行情況，對異常電源波動進行實時報警，實現(xiàn)分布式檢測數(shù)據(jù)的遠程采集監(jiān)控。近幾年出現(xiàn)一種基于無線網(wǎng)絡的遠程電源監(jiān)控技術——無線電源檢測網(wǎng)絡(Wireless Resource Sensor Network，WRSN)［1］，具有部署簡便、維護成本低等優(yōu)點，可廣泛應用于工業(yè)電源監(jiān)控、商用電源監(jiān)控和樓宇自動化等方面，已成為目前國內外智能儀表與物聯(lián)網(wǎng)交叉領域的研究熱點。

1 WRSN模型分析與多蟻群算法設計

1.1 WRSN網(wǎng)絡的特性

WRSN網(wǎng)絡應具有如下典型設置:①基于Wifi協(xié)議，路由在MAC層與IP層中解決;② 所有節(jié)點都是同構的，具備數(shù)據(jù)融合的功能;③無線鏈路是對稱的，上下行帶寬相同;④ 節(jié)點之間不存在固定的物理位置對應，節(jié)點的鄰近關系可隨應用變動。因此下面在一個無線電源監(jiān)控網(wǎng)絡中，針對單節(jié)點跳轉傳輸延遲時間這個指標來設計特定的路由控制算法，以滿足真實工程應用需求。

1.2 基于蟻群聚類的優(yōu)化路由算法設計

1.2.1 蟻群算法

ACA是20世紀90年代初期提出的一種新型模擬進化算法［2－4］，具有很強的可擴展性和魯棒性，適應動態(tài)環(huán)境，適用于動態(tài)網(wǎng)絡路由設計?；鞠伻旱乃惴ù嬖谑諗克俣容^慢及易陷入局部最優(yōu)等缺陷，所以在實際工程中需要進行優(yōu)化。目前網(wǎng)絡路由蟻群優(yōu)化算法包括:移動自組網(wǎng)的ARH算法、ABC算法、ASGA算法和自適應分布式 AntNet算法［5－8］。這里針對WRSN提出了一種并發(fā)蟻群算法，實現(xiàn)網(wǎng)絡資源的均衡優(yōu)化及路由的魯棒性。

1.2.2 多同質蟻群間信息素吸引因子與排斥因子設計

在一個多蟻群算法模型中，信息素的吸引因子與排斥因子為不同蟻群間數(shù)據(jù)信息交流的閾值，直接影響模型計算性能。這里提出一種特定的吸引因子與排斥因子定義。設表示種群k中第i只螞蟻代理，同種群內的螞蟻均釋放同一種類型的信息素，不同種群釋放的信息素類型不同。則為種群k的螞蟻當前位于傳感器節(jié)點i，在其鄰域Πi內選擇下一個節(jié)點j的k類型信息素的吸引因子，則

式中，τij為邊(i，j)上的第k種信息素濃度。

式中，τij為邊(i，j)上的第k種信息素濃度。當位于節(jié)點i的螞蟻在其鄰域Πi內根據(jù)概率轉移規(guī)則選擇下一個傳感器節(jié)點i時，該螞蟻會以更高的概率選擇具有較高自己類型信息素濃度的路徑。

1.2.3 多同質蟻群間概率轉移規(guī)則

在蟻群計算模型中，種群中螞蟻選擇下一步路由的轉移概率規(guī)則也是算法模型的重要組成部分。這里采用的規(guī)則為:種群S中位于傳感器節(jié)點i的螞蟻選擇下一節(jié)點j進行路由時的轉移概率表達式為:

1.2.4 螞蟻的信息素更新策略

在蟻群進行路由搜索時，前向螞蟻的信息素更新策略也是重要的設計要素。由于無線網(wǎng)絡的結構不確定性，因此在設計更新策略時，需考慮局部網(wǎng)絡情況與全局網(wǎng)絡情況，提出不同的更新策略。種群中的前向螞蟻根據(jù)本種群的信息素轉移到下一個節(jié)點后，局部更新該種群的信息素。局部更新規(guī)則為:

式中，ρ為信息素揮發(fā)后的殘留因子。在螞蟻經(jīng)過的路徑上采用蟻密模型的更新模式，即前向螞蟻在經(jīng)過的路徑(i，j)上釋放的信息素量為每單位長度Q，

式中，Q為一常數(shù)。當前向螞蟻到達目的節(jié)點后，將收集到的從源節(jié)點到目的節(jié)點的路徑信息記錄下來，并通過測試消息轉移給后向螞蟻，自身將被刪除。逆向螞蟻更新的規(guī)則為:

式中，R為種群S中的螞蟻k在一次循環(huán)結束后路徑上的網(wǎng)絡資源消耗值。

1.3 多蟻群并行路由優(yōu)化算法流程

綜合上述分析，設計多蟻群并行路由優(yōu)化算法流程如下:

①選擇子匯聚節(jié)點。從靠近基站的傳感器節(jié)點中選擇子匯聚節(jié)點，由所需的子匯聚節(jié)點數(shù)和各個傳感器節(jié)點已成為子匯聚節(jié)點的次數(shù)來決定。

②多蟻群算法初始化。算法將從源節(jié)點出發(fā)代表網(wǎng)絡流量的螞蟻劃分成k個子群，為每個子群分配一個相應的子匯聚節(jié)點作為目的節(jié)點。將網(wǎng)絡中的螞蟻分為前向螞蟻和后向螞蟻并初始化螞蟻的禁忌表，后向螞蟻在返回源節(jié)點的過程中對路徑進行全局更新。

③多蟻群并行優(yōu)化計算。并行計算各蟻群的信息素吸引因子、排斥因子、蟻群概率轉移規(guī)則與信息素更新策略，并刷新當前蟻群的配置參數(shù)，當后向螞蟻返回到源節(jié)點后出動第2批螞蟻，直至達到算法最大迭代次數(shù)NCmax時跳出循環(huán)。結束時，每個種群可以得到一條優(yōu)化路徑，多個種群可得多個路徑。

④根據(jù)無線網(wǎng)絡的指標來對蟻群所得的路由進行比較，如未符合實際工程需求則返回步驟②再次進行蟻群初始化與計算，直至找到合適的路由結果。

2 仿真實驗

下面在Matlab 2010b上對設計的基于多蟻群算法的負載感知和高效接入跨層路由協(xié)議進行實驗。感知區(qū)域為(0，0)到(1 000，1 000)的平面正方形監(jiān)測區(qū)域，隨機散布M=50個被控電源節(jié)點，仿真時間為T=1 000 s。

考慮到傳感器網(wǎng)絡節(jié)點的現(xiàn)實情況，將節(jié)點最大傳輸距離設為L=100 m，控制數(shù)據(jù)幀平均大小為Sframe=512 B，系統(tǒng)緩沖區(qū)隊列長度為Lframe=100數(shù)據(jù)包的長度，MAC層采用IEEE802.11協(xié)議。多蟻群算法的迭代次數(shù)NCmax固定為$200$代，匯聚節(jié)點個數(shù)或種群個數(shù)k=3。其他參數(shù)取值采用經(jīng)驗的方法設置為:每個種群中的螞蟻個數(shù)m=100，ε =0.85，α =3，β =2，ρ=0.2，Q=100。運行經(jīng)典蟻群算法和本文優(yōu)化蟻群算法對無線電源監(jiān)控網(wǎng)絡路由進行計算，取n=10次實驗結果的平均值進行比較。

用本文算法和經(jīng)典算法對重負荷無線電源監(jiān)控網(wǎng)絡進行路由優(yōu)化時，最優(yōu)路徑上數(shù)據(jù)包從源節(jié)點到目的節(jié)點所需平均傳輸時延大小比較如圖1所示。從仿真結果可見，當網(wǎng)絡達到穩(wěn)定時，經(jīng)典算法的數(shù)據(jù)包延遲比多種群蟻群算法要大，達到穩(wěn)定狀態(tài)需要較長的時間且波動大，因此本文采用改進的多種群蟻群算法在進行無線電源監(jiān)控網(wǎng)絡路由跨層優(yōu)化時，具有傳輸時延小、收斂速度快且傳輸較為穩(wěn)定等明顯優(yōu)勢。

圖1 數(shù)據(jù)包單點延遲時間仿真實驗數(shù)據(jù)

3 結束語

上述采用一種智能優(yōu)化的多蟻群算法對WRSN進行跨層路由優(yōu)化。仿真實驗證明，該算法得出的最優(yōu)傳輸路徑能夠滿足無線電源監(jiān)控網(wǎng)絡的實時性、可靠性及負載平衡等方面的要求，保證了無線電源監(jiān)控網(wǎng)絡的服務質量。該技術適用于物聯(lián)網(wǎng)環(huán)境，為其他有線網(wǎng)絡系統(tǒng)轉向物聯(lián)網(wǎng)系統(tǒng)提供了有益的探索實踐經(jīng)驗。

［1］孫浩明.無人值守無線傳感器網(wǎng)絡電源系統(tǒng)管理［J］.通信電源技術，2009(2):34－36.

［2］王 鶴，任建華，邱云飛.基于蟻群聚類的智能優(yōu)化算法及應用［J］.遼寧工程技術大學學報(自然科學版)，2010(S1):11－14.

［3］馬春英，曹安得，周允征.蟻群聚類組合的改進算法［J］.沈陽建筑大學學報(自然科學版)，2011(4):21－25.

［4］DING Shifei，ZHANG Yongping.Research on a Principal Components Decision Algorithm Based on Information Entropy［J］.Journal of Information Science，2009，35(1):102－104.

［5］暢福善.移動計算環(huán)境中基于蟻群算法的路徑選擇［J］.微計算機信息，2009(2－3):272－273.

［6］ABRAHAM A，RALNOS V.ANTIDS:Self Organized Ant-Based Clustering Model for Intrusion Detection System［C］∥The Fourth IEEE Imitational Workshop on Soft Computing as Trans Disciplinary Science and Technology(WSTST05).Japan:SpringerVerlag，2005:157 －168.

［7］王 玨，周志華，周傲英.機器學習及其應用［M］.北京:清華大學出版社，2006.

［8］陸廷榮，馬玉書，楊永田.基于層次尋址擴展IP網(wǎng)地址空間的研究［J］.計算機工程，2006(8):128－130.