基于蟻群算法和BP神經網絡的信道分配策略的研究*

翟學明，王　佳，李金澤（華北電力大學（保定）控制與計算機工程學院，河北保定071003）

?

基于蟻群算法和BP神經網絡的信道分配策略的研究*

翟學明*，王佳，李金澤
（華北電力大學（保定）控制與計算機工程學院，河北保定071003）

摘要：研究無線傳感器網絡信道分配策略的主要目標是提高網絡吞吐量和容量，減小網絡的傳輸時延，最大限度的利用有限的網絡帶寬資源。多信道MAC協議的應用，可以有效地提高網絡通信的可靠性和吞吐量，以及解決由于信道受干擾而造成的網絡癱瘓等問題。根據無線傳感器網絡多信道的特點提出了一種基于蟻群算法的動態反饋負載均衡信道分配策略。本策略首先應用BP神經網絡對信道負載情況進行預測，然后通過基于蟻群算法的負載均衡算法對信道進行篩選，最后利用最大離散化算法進行信道分配。在NS2平臺下對所設計的協議進行了仿真實現，并與應用最為廣泛的多信道MMAC協議以及SMAC進行了對比分析。根據仿真結果可知，本文設計的MAC協議在網絡吞吐量、網絡傳輸時延等性能方面比MMAC協議及SMAC都有了很大程度的提升。可以有效減小網絡傳輸時延，提高網絡吞吐量和抗干擾能力。

關鍵詞：無線傳感器網絡；信道分配機制；蟻群算法；BP神經網絡；最大離散化；NS2仿真

項目來源：國家自然科學基金項目（60974125）

目前，無線傳感器網絡在實際應用中主要采用單信道MAC協議，它簡化了協議的實現方式，降低了節點間相互發現的難度，使得組網更加迅速、便利。但是當數據量非常大時，眾多節點將會同時對這條信道提出通信申請，造成通信競爭加劇［1］。節點之間干擾嚴重，并發性強時還可能導致嚴重的沖突，并影響數據傳輸的可靠性［2］。此外，無線傳感器網絡工作在2.4 GHz ISM頻段，如果周圍存在WiFi等無線網絡，它們共用這一頻段，無線信道開放共享的特征可能會引起單信道傳感網絡與這些無線網絡之間的相互干擾［3］。

多信道協議可以使無線傳感器網絡的眾多節點利用多個信道進行并行通信，從而大大提高了網絡帶寬資源的利用率，減少了通信競爭，提高了網絡通信的吞吐量。同時，當某一個信道受到干擾時，節點可以使用其他信道進行通信，提高了網絡的抗干擾能力［4］。

通過對多信道MAC層的通信協議進行改進來提高網絡的服務質量已經成為當前研究的熱點［5］。文獻［6-8］應用低復雜度的貪心算法實現信道的分配，并從無線信道分配策略以及對網絡吞吐量、時延的影響等方面進行了研究。研究結果表明利用貪心算法模型能夠能夠使信道分配達到局部最優分配的目的。但是當網絡中節點數量眾多，且節點密度大時，往往不能達到令人滿意的效果，網絡的QOS會下降的特別明顯。其原因在于貪心算法不能達到全局最優分配的目的。文獻［9］提出了基于虛擬鏈路的多信道協議，能夠很好的避免信道干擾，但是沒有很好的解決時間同步問題。文獻［10］提出了一種基于忙音的IABTM（Interference-Aware Busy Tone based Multi-Channel MAC Protocol）協議。該協議使用忙音信道傳遞控制信息可以很好的解決多信道協議存在的隱終端、暴露終端以及“Deaf?ness”等問題，提高了網絡的吞吐量。但是這種MAC協議在每次數據傳輸前，所有的節點都監聽同一個控制信道，發送節點和接收節點首先跳轉到同一個控制信道協商傳輸控制信息，以便節點間無干擾通信。由于該協議僅預留了一個控制信道來傳遞控制信息，節點數目較多且網絡中要同時傳輸數據的節點對較多時，控制信息之間容易發生較為嚴重的沖突。

基于以上分析，本文提出一種基于BP神經網絡與蟻群算法的動態反饋負載均衡信道分配策略。該策略的核心思想為：在數據傳輸的過程中，首先根據BP神經網絡的基本原理，通過反饋得到下一階段可能不存在干擾的信道。然后應用基于蟻群算法的負載均衡策略對信道進行篩選，將不存在干擾且負載較小的信道序列記錄在優先選擇列表PCL（Priority Choice Lists）中。然后應用最大離散化的算法從PCL中選擇信道進行信道離散化，信道最大離散化完成之后，將信道序列分配給有通信請求的節點對。

1　協議算法

多信道協議的執行過程主要分為信道預測、信道篩選以及信道分配等3個主要過程［11］。

1.1信道預測

在信道預測方面，本文采用BP神經網絡可靠性預測機制。信道可靠性預測機制BP神經網絡預測模型如圖1所示。

圖1　信道可靠性預測機制BP神經網絡預測模型

以理想因子m、當前信道列表CCL（Current Channel List）、接收信號強度指示的標準差δRSSI作為輸入量，以優先選擇信道列表PCL、接收信號強度的退化量ΔRSSI以及丟包率的退化量ΔPLR作為輸出量。根據神經網絡系統的研究成果可知，隱層的節點如果取足夠多的數量，單一隱層的神經網絡便可以滿足逼近非線性函數的精度要求，因此本文只應用了一個隱層。

BP神經網絡通過對連接權值的調整完成自我學習的功能。BP神經網絡的自我學習過程主要包括信號的前向傳遞過程和誤差的反饋過程［12］，信號前向傳遞過程如式（1）所示：

式中netj和netk分別表示模型中隱層節點和輸出層節點的凈輸入量，xi和yk分別表示模型的輸入和模型的輸出，M和N分別表示模型中輸入層節點的個數和隱層節點的數量，Wij和Wjk表示模型中輸入層、隱層以及輸出層之間連接時的權重，Oj表示模型中隱層節點產生的輸出，f表示功能函數，f采用sig?moid函數：

式（2）中θ表示節點閾值。

網絡的誤差函數可以用式（3）表示：

式（3）中L表示輸出層節點的數量，dk表示期望得到的輸出。

本文采用使誤差梯度函數的方向下降的方法修正網絡中的權值，從而達到誤差反饋的目的。輸入層和隱層誤差反饋的權重設置如下：

式（4）中，μ表示學習速率，0<μ

輸出層和隱層誤差反饋的權重設置如下：

模型中閾值的修正量如下：

在算法初始化時，預先設定閾值與權重。然后根據輸出的接收信號強度的退化量ΔRSSI以及丟包率的退化量ΔPLR的值不斷地對閾值和權值進行調整。直到ΔRSSI及ΔPLR值滿足要求，或者算法的學習次數超過設定的限定值退出。

經過BP神經網路多次自我學習之后，預測算法預測的信道序列接收信號強度指示的標準差與實際的信道序列接收信號強度指示的標準差的關系如圖2所示。

圖2　接收信號強度指示標準差的預測值與實際值的關系圖

2.2基于蟻群算法的負載均衡

蟻群優化算法ACO（Ant Colony Optimization algorithm）是一種啟發式搜索的算法，算法從初始狀態開始根據啟發條件不斷向全局最優的解空間逼近，直到找到全局最優解為止。這里蟻群算法的啟發條件就是一種被稱為信息素的物質［13］，在本文算法中指的是單一信道的負載占總負載的比重。

2.2.1負載均衡對無線傳感網絡性能的影響

負載均衡問題對于無線傳感器網絡信道分配來說就是使數據業務均衡的分配給各個信道。負載均衡對于無線傳感器網絡的總吞吐量、平均時延的性能都十分關鍵。尤其是對于總吞吐量性的作用更加明顯。原因在于，如果網絡負載不能均衡分布時，負載過大信道會導致數據業務的積壓，而負載較小的信道會產生信道在傳輸完數據業務后空閑的現象，從而影響無線傳感網絡的總吞吐量［14］。

2.2.2基于蟻群算法的負載均衡算法

本文設計了低開銷的跨MAC層與網絡層設計的蟻群系統優化算法。跨MAC層與網絡層算法設計的思想為：使數據鏈路層、網絡層之間進行信息的融合與交流，建立一定的聯系，協同地工作，去除冗余操作，更有效地分配網絡資源、提高網絡性能優化的效率。從鏈路層統計獲得的接收信號質量指示RSSI，負載度等參數與路徑延遲、跳數等參數一并作為路由選擇的依據，根據由以上參數定義的路由代價函數作為低開銷的蟻群算法的啟發因子。為了減小開支算法在路由層應用了三種全新的機制：在路由發現階段，采用新的廣播機制，每個節點向它的鄰居節點廣播一個控制信息，但是只有其中的一個節點再次廣播這個消息；在路由維護階段，使用數據包只更新活躍路徑的信息，從而進一步降低開銷；在路由恢復階段，采用深度搜索的方法來修復路徑，該算法在斷開鏈路兩端的節點之間嘗試用深度搜索發現新路徑。

在MAC層，本文設計了基于蟻群算法的負載均衡信道分配策略。算法中信息素更新分為迭代最優更新和局部信息素更新。搜索解空間的搜索路徑選擇的方法包括按先驗規律和按概率選擇兩種。本算法的目的是：在某一時刻，當網路中的數據業務集到來之時，利用蟻群系統算法找到一個使得負載最均衡分布的信道分配序列。信道負載分配是否均衡可以用信道負載分布的標準差來表示：標準差B為負載均衡度。式（7）中j表示可用信道的總量，xj表示信道j的負載比，q表示信道的平均負載比，B表示信道負載比的標準差。B越小表示信道負載的波動越小，負載分布越均衡。算法優先為低負載的信道更新信道負載比。而隨著整體負載的上升，更新機制逐步放開負載比更新的限制條件，讓更多相對負載比較高的信道加入到算法調度中；當系統負載下降，則又會在全局更新中關閉個別負載比較高的信道的調度。從而達到整體負載均衡的目的。

①迭代更新公式

在本協議中i（r，s）表示信道rs上的信息素含量，即信道rs的負載量占總負載量的比值，Δi(r,s)表示信道上的負載占總負載總量比值的增量，ρ表示迭代最優更新負載比的揮發因子，（1-ρ）表示跟新負載比的殘留因子。通過改變ρ和K的取值調整信道負載增長的速度。σ(r,s)表示每次迭代產生最優信道序列負載的標準差，IOP（Iterative Optimal Path）表示迭代最優路徑。

②局部更新公式?表示局部更新負載比的揮發系數，(0)表示負載比的初值，?的引入可以減少被選擇過的信道上的負載比，有利于新路徑的發現。

③路徑轉移規則公式q0(0q0時，按照概率對信道進行搜索。當q≤q0時按照先驗規律選擇信道。

④轉移概率計算公式

式（12）中，Pkij(t)表示第k螞蟻在t時刻選擇信道ij的概率，allowedk表示所有與i節點有邊相連的節點集合，即第k只螞蟻在節點i處可選擇的節點集合，如果節點在該集合之中，則其概率按負載比的濃度進行計算；反之，其概率為0。轉移概率公式表示某一次迭代的第k只螞蟻按照該信道負載占總負載的比例計算出的，如果該信道的負載占總負載的比重越大，則其轉移的概率也越大。

基于蟻群算法的無線傳感器網路多信道負載均衡調度算法的算法描述如表1所示。

表1　算法的負載均衡調度算法

2.3信道最大離散化

信道的最大離散化，將優先選擇列表中的信道以公式（13）的方法進行最大離散化并分為4組：

G(i)=[i+0H,i+1H,i+kH] i=1,2,3,4 k=3（13）式（13）中，k表示滿足不等式i+kH≤16的最大值。每組至少包括n個信道，如式（14）所示。

為了保證頻段最大離散化能夠最大限度的分開每組信道。第j組的信道表示如式（15）所示：

例如，某一時刻PCL中的信道依次為：1、3、4、6、8、9、11、12、14，則經過最大離散化算法得到的信道分配序列為：3、9、6、12、1、8、14、4、11。信道最大離散化完成。當有節點對要進行數據傳輸時，則從最大離散化之后的信道列表中根據貪心著色算法選擇信道分配給節點對。

3　實驗與仿真分析

為了對本文設計的MAC協議（在下文中記為MDMAC）的性能進行驗證和評估，在NS2仿真平臺上分別對本文提出的MDMAC協議、SMAC協議以及MMAC協議從網絡總吞吐量、平均時延、丟包率等方面進行仿真測試和協議性能分析，從而驗證本文提出的MDMAC協議的高效性。考慮到成本的因素，本協議適用于單收發器的節點，因此在仿真過程中，把節點設置為半雙工工作模式。

3.1仿真配置

在NS2仿真平臺中需要定義無線節點的參數，如表2所示。網絡的仿真拓撲結構圖如圖3所示。

表2　無線節點參數設置

圖3　網絡拓撲結構圖

3.2性能分析

圖4能夠看出，當包到達速率處于較低的水平時，MDMAC與SMAC及MMAC的吞吐量接近，這是由于網絡負載較小時單信道協議可以滿足網絡的傳輸要求，不會發生嚴重的數據沖突；而當包到達速率高于某個臨界值時，MDMAC協議的吞吐量明顯高于SMAC協議及MMAC協議，而且隨著包到達速率的不斷增加，MDMAC協議的吞吐量增大的比SMAC協議及MMAC協議越來越明顯。這是因為MDMAC協議應用蟻群算法實現負載的均衡分布，以及基于BP神經網絡的信道預測機制降低了信道相互干擾的幾率，使無線信道的頻譜資源得到了充分的利用，從而提升了無線網絡的吞吐量性能。

圖5對比了MDMAC協議、SMAC協議以及MMAC協議在包到達速率發生變化的情況下網絡平均時延的性能。從圖中可以看出，當網絡負載較低時，即包到達率較小時，三種MAC協議的網絡平均時延都較小。但是多信道的MDMAC以及MMAC協議的平均時延要比SMAC的平均時延高，這是因為當網絡負載較小時，單信道SMAC協議能夠滿足網絡傳輸的需求，并且與MDMAC協議及MMAC協議相比不存在信道協商與切換的時延。而當網絡負載增大時，包到達率超過某個特定值時，三種MAC協議的網絡平均時延均增大。但是MDMAC協議平均時延的增長速度明顯比SMAC協議及MMAC協議小。這是由于SMAC協議及MMAC協議均采用退避機制，網絡負載較高時網絡沖突節點的退避時間增大。而MDMAC協議能夠根據信道的質量動態的進行信道切換，應用BP神經網絡算法預測信道質量，并通過最大離散化的算法降低信道間的干擾以及沖突的發生概率。與本文設計的MDMAC協議相比，MMAC協議可能會持續的競爭信道直到競爭失敗，這樣就會造成網絡的平均時延大大升高。由此可見本文設計的MDMAC協議的網絡平均時延性能高于SMAC協議及MMAC協議。

圖4　靜態網絡中吞吐量與包到達速率的關系

圖5　靜態網絡中分組平均延遲與包到達速率的關系

通過對網絡節點數據包發送速率進行調節，測試得到的丟包率結果如圖6所示。由圖可見網絡節點發送速率較快即網絡負載較重時，由于信道中的數據包量大而造成較大的碰撞和丟包率，導致了較為嚴重的網絡擁塞。尤其是在使用單信道的SMAC協議中，丟包率的增加更為明顯。而MDMAC協議及MMAC協議由于采用了多信道機制，有效降低了網絡擁塞程度，降低了網絡中的數據包碰撞概率。與MMAC協議相比，本文設計的MDMAC協議采用了基于BP神經網路的最大離散化信道分配策略，最大限度的減少了信道相互干擾的可能性以及數據碰撞的概率。綜合來看，MDMAC協議比目前應用最為廣泛的單信道的SMAC協議及典型的多信道MMAC協議具有更小的丟包率。

圖6　不同發送速率下丟包率

4　結束語

在實際應用中，網絡環境可能是復雜多變的。網絡拓撲結構、節點間的干擾以及外界干擾如WiFi

信號的干擾都可能時刻在發生著變化。而上述問題在本文設計的MDMAC協議中都沒有進行深入的探討與分析研究。所以，為使本文提出的MD?MAC協議在網絡拓撲結構發生快速變化及外界干擾環境復雜等情況下，網絡性能仍然具有較高的可靠性，仍然存在很多問題需要研究與分析。

參考文獻：

［1］任昊翔，郭達偉，邵凝寧.一種新型的無競爭的基于TDMA的MAC協議［J］.傳感技術學報，2013，26（1）：89-94.

［2］張招亮，陳海明，黃庭培.無線傳感器網絡中一種抗無線局域網干擾的信道分配機制［J］.計算機學報，2012，35（1）：504-517.

［3］Zhang X，Shin K G. Enabling Coexistence of Heterogeneous Wire? less Systems：Case for ZigBee and WiFi［C］//Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Network?ingand Computing（MobiHoc）. 2011：231-154.

［4］張龍妹，史浩山，陸偉. DTFMM：一種適應于WMSNs的多信道MAC協議［J］.傳感技術學報，2011，24（3）：452-457

［5］張娜，陳曙.無線局域網MAC層協作通信改進方案［J］.傳感技術學報，2012，25（2）：283-288

［6］王豐亮，呂衛鋒，諸彤宇.基于貪心策略的多信道數據廣播調度算法［J］.計算機工程，2011，12：179-181

［7］Wu X，Srikant R. Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks［C］//Proc IEEE Info?com，2006：595-605.

［8］秦紹華.無線傳感器網絡多信道技術的研究［D］.山東大學，2014：23-36.

［9］Juan L，HaiBo L，RenFa L. VL-MAC：Virtual Link Based Multichannel MAC Scheme in WSN［C］//Information Technology：New Generations，2009. ITNG’09. Sixth International Conference on. IEEE，2009：1600-1601.

［10］李鎣.無線自組織網MAC層協議關鍵技術的研究［D］.上海：上海交通大學，2007：41-66.

［11］Lei Hongjiang，Gao Chao，Guo Yongcai. Survey of Multi-Channel MAC Protocols for IEEE 802.11-Based Wireless Mesh Networks ［J］. The Journal of China Universities of Posts and Telecommuni?cations，2011（2）：33-44.

［12］孔玉靜，侯鑫，華爾天.基于BP神經網絡的無線傳感器網絡路由協議的研究［J］.傳感技術學報，2013，26（2）：246-251.

［13］Dorigo M，Maniezzo V，Colorni A. The Ant System：Optimization by a Colony of Cooperatingagents［J］. IEEE Transactions on Sys?tems，Man and Cybernetics-PartB，1996，26（1）：29-41.

［14］王璟，王利利，游金闊.基于動態配置等價多路徑技術的無線傳感器網絡負載均衡算法研究［J］.傳感技術學報，2015，28 （5）：752-756.

翟學明（1967-），男，博士，副教授，主要從事電力系統自動化在線監測技術、絕緣監測技術、計算機網絡及其應用的研究，zxm3165@126.com；

王佳（1989-），男，碩士研究生，2013年就讀于華北電力大學（保定）控制與計算機科學學院計算機系，主要研究方向為無線傳感器網絡，1069695617@qq.com。

Research on Channel Allocation Strategy Based on Ant Colony Algorithm and BP Neural Network*

ZHAI Xueming*，WANG Jia，LI Jinze
（School of Control and Computer Engineering，North China Electric Power University，Baoding Hebei 071003，China）

Abstract：The main purpose of studying channel allocation strategy of wireless sensor network is to improve net?work throughput and capacity，reduce transmission delay of the network，and use the limited network bandwidth re?sources efficiently. Application of multi-channel MAC protocol can solve the problem of network paralysis caused by channel interference. Due to the characteristics of the wireless sensor network，this article proposed a dynam?icfeedback load balancing channel allocation strategy based onant colony algorithm. This strategy applied BP neural network to predict the channels’load，then filtered the channels by using the load-balancing algorithm based on ant colony，finally allocated the channel sequences by using the maximum discrete channel allocation algorithm. Final?ly，this protocol wassimulated and implemented on NS2 platform，and it was also compared with the MMAC protocol and the SMAC protocol. According to the simulation，the MAC protocol we proposed in this paper performed better than the MMAC protocol and the SMAC protocol in terms of network throughput，network delay to a large degree of improvement. It can effectively reduce the network delay，increase network throughput and enhance the anti-jam?mingcapability.

Key words：wireless senor network；multi-channeldistribution mechanism；ant colony algorithm；BP neural net?work；maximum discrete；NS2 simulation

doi：EEACC：1295；6150P；723010.3969/j.issn.1004-1699.2016.03.024

收稿日期：2015-08-22修改日期：2015-12-03

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）03-0445-06