基于蟻群的無線電源管理網絡路由算法

姜福祥，錢建波，于正永

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

0 引言

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

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

1.1 WRSN網絡的特性

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

1.2 基于蟻群聚類的優化路由算法設計

1.2.1 蟻群算法

ACA是20世紀90年代初期提出的一種新型模擬進化算法［2－4］，具有很強的可擴展性和魯棒性，適應動態環境，適用于動態網絡路由設計。基本蟻群的算法存在收斂速度較慢及易陷入局部最優等缺陷，所以在實際工程中需要進行優化。目前網絡路由蟻群優化算法包括:移動自組網的ARH算法、ABC算法、ASGA算法和自適應分布式 AntNet算法［5－8］。這里針對WRSN提出了一種并發蟻群算法，實現網絡資源的均衡優化及路由的魯棒性。

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

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

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

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

1.2.3 多同質蟻群間概率轉移規則

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

1.2.4 螞蟻的信息素更新策略

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

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

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

式中，R為種群S中的螞蟻k在一次循環結束后路徑上的網絡資源消耗值。

1.3 多蟻群并行路由優化算法流程

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

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

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

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

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

2 仿真實驗

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

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

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

圖1 數據包單點延遲時間仿真實驗數據

3 結束語

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

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

［2］王 鶴，任建華，邱云飛.基于蟻群聚類的智能優化算法及應用［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］暢福善.移動計算環境中基于蟻群算法的路徑選擇［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網地址空間的研究［J］.計算機工程，2006(8):128－130.