當前位置:首頁 > 工業(yè)控制 > 工業(yè)控制
[導讀]隨著無線通信技術、電子技術、傳感器技術和微電系統(tǒng)的飛速發(fā)展,無線傳感器網(wǎng)絡的研究越來越受到人們的重視。傳感器網(wǎng)絡是由部署在觀測環(huán)境內(nèi)的大量微型傳感器節(jié)點通過無線通信方式組成的一種無線網(wǎng)絡。組成傳感器網(wǎng)

隨著無線通信技術、電子技術、傳感器技術和微電系統(tǒng)的飛速發(fā)展,無線傳感器網(wǎng)絡的研究越來越受到人們的重視。傳感器網(wǎng)絡是由部署在觀測環(huán)境內(nèi)的大量微型傳感器節(jié)點通過無線通信方式組成的一種無線網(wǎng)絡。

組成傳感器網(wǎng)絡的節(jié)點包括傳感器和匯聚節(jié)點(Sink)。傳感器節(jié)點的能量十分有限,并且在部署后難以再次補充能量,因此傳感器網(wǎng)絡存在嚴重的能量約束問題[1]。

參考文獻[2]提出一種無線傳感器網(wǎng)絡AODV(AdhocOn-DernandDistanceVector)路由協(xié)議改進方案,通過改進RREQ協(xié)議幀,使節(jié)點的剩余能量值參與到路徑中,優(yōu)化RREQ洪泛傳播。但該算法是基于單路徑數(shù)據(jù)傳輸,沒有考慮節(jié)點的負載狀況,節(jié)點容易產(chǎn)生擁塞,導致數(shù)據(jù)包的重傳或數(shù)據(jù)丟失的情況。

參考文獻[3]提出了一種基于蟻群優(yōu)化的路由算法ARAWSN(ACO-BasedRoutingAlgorithmforWirelessSensorNetworks),該算法在定向擴散協(xié)議的基礎上,通過搜尋螞蟻以廣播的方式在網(wǎng)絡中擴散建立起源節(jié)點到目的節(jié)點的多條路徑的路由表。

利用蟻群算法的轉(zhuǎn)移概率的方式來進行路徑的選擇,從而平衡網(wǎng)絡中節(jié)點能量的消耗。該算法建立了所有到目的節(jié)點的路徑,存在很大的冗余,影響網(wǎng)絡的實時性,且在路由建立過程中采用洪泛的方式導致網(wǎng)絡的路由開銷比較大。

參考文獻[4]綜合考慮了均衡傳輸能量消耗和節(jié)點剩余能量,提出了多種群蟻群優(yōu)化路由算法MACO(MultiAntColonyOptimization)。該算法優(yōu)化了基本蟻群算法的螞蟻前向移動的選擇概率模型,同時利用多種群獲得多條優(yōu)化路徑。但該算法需要進行多次迭代,且可能陷入局部最優(yōu)解,影響網(wǎng)絡數(shù)據(jù)傳輸?shù)膶崟r性。

針對上述路由算法及其存在的不足,本文提出了基于蟻群算法的無線傳感器網(wǎng)絡按需多路節(jié)能路由算法MP-ACA(On-demandMulti-pathandPower-savingAntColonyAlgorithm)。該算法結(jié)合蟻群算法和AODV路由協(xié)議,能夠在源節(jié)點和目的節(jié)點之間建立起多條鏈路不相關路由,并改善了蟻群算法在無線傳感器網(wǎng)絡中查找路由的多次迭代的策略,有效地減少了擁塞頻率、降低了路由的開銷,同時均衡了節(jié)點的能量開銷,延長了網(wǎng)絡的生命周期。

1 蟻群算法簡介

1.1 基本蟻群算法原理

蟻群算法[5]ACA(AntColonyAlgorithm)是一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法,其基本原理可大致描述如下:自然界螞蟻會在所經(jīng)過的路徑上釋放一定的信息素,后來的螞蟻會根據(jù)信息素強度來選擇路徑,信息素強度越大的路徑被選擇的概率越大,于是就形成了一種正反饋機制,最終螞蟻會選擇信息素最大的最短路徑。蟻群算法通過釋放“人工螞蟻”來模擬自然螞蟻的行為以完成上述的選優(yōu)過程。

1.2 蟻群算法

根據(jù)螞蟻覓食的基本原理,科學家們設計了尋找最優(yōu)路徑的蟻群算法,其主要步驟為:

2 按需多路節(jié)能路由算法設計

針對無線傳感器網(wǎng)絡數(shù)據(jù)多跳傳輸、節(jié)點能量有限等特性,本文對基本蟻群算法和MACO算法進行改進,并結(jié)合AODV路由協(xié)議,賦予螞蟻新的特性和路徑搜索方式。下面介紹本文研究中使用的相關定義。

定義1:從源節(jié)點到目的節(jié)點的路徑搜索螞蟻稱作前向螞蟻,它執(zhí)行路徑搜索功能,并建立反向信息素表。

定義2:前向螞蟻到達目的節(jié)點后,從目的節(jié)點返回到源節(jié)點的螞蟻稱作后向螞蟻,它執(zhí)行信息素更新功能,并建立路由表。

定義3:前向螞蟻在路徑搜索過程中,到達某一節(jié)點后建立的指向源節(jié)點的路由表稱作反向信息素表,該表包括源節(jié)點、下一個節(jié)點、反向節(jié)點信息素τ(j,i)。

2.1 算法設計思想

MP-ACA算法在Ant-Net算法[6]的基礎上,將螞蟻分為前向螞蟻和后向螞蟻。為了實現(xiàn)不同節(jié)點的能量消耗均衡,MP-ACA算法中,將前向螞蟻要訪問的節(jié)點的剩余能量作為影響信息素濃度的一個參數(shù)。MP-ACA算法通過m只前向螞蟻同時獨立地進行路徑搜索,并建立反向信息素表。

當每個前向螞蟻到達目的節(jié)點時,它們將立即轉(zhuǎn)化成一個后向螞蟻,后向螞蟻根據(jù)反向信息素表反向回到源節(jié)點后一次路由建立完畢,建立起信息素路由表以代替?zhèn)鹘y(tǒng)的網(wǎng)絡節(jié)點路由表,并采用一種新的信息素規(guī)則進行信息素更新。

同時MP-ACA算法在極大-極小蟻群算法[7]上將各條路徑上的信息素濃度限制在[τmin,τmax]之間,τmin可以有效地避免算法停滯,τmax避免某條路徑上的信息素遠大于其他路徑,使所有的螞蟻都集中到同一條路徑上面,限制算法的擴散。在MP-ACA算法中,前向螞蟻轉(zhuǎn)移規(guī)則、信息素更新規(guī)則詳細設計如下。

2.2 前向螞蟻轉(zhuǎn)移規(guī)則

為了均衡網(wǎng)絡中節(jié)點的能量消耗,MP-ACA算法在蟻群算法的基礎上,新加入兩節(jié)點間的剩余能量因子改進前向螞蟻轉(zhuǎn)移規(guī)則。改進后的算法在螞蟻尋找最短路徑的同時受到了節(jié)點能量消耗的限制。MP-ACA算法中處于節(jié)點i的螞蟻k選擇下一節(jié)點j進行訪問的概率pkij使用以下公式確定:

式中,W(j)是節(jié)點j的剩余能量;JK(i)代表了位于節(jié)點i的前向螞蟻k允許訪問的鄰居節(jié)點集合。在這里定義滿足以下兩個要求的節(jié)點j將會屬于JK(i):(1)節(jié)點j還未被螞蟻k訪問;(2)節(jié)點j比前一節(jié)點i距離目的節(jié)點更近,且距離源節(jié)點更遠。

MP-ACA算法采用改進的轉(zhuǎn)移規(guī)則,簡化了MACO算法使得MP-ACA更適用于無線傳感器網(wǎng)絡。同時前向螞蟻在尋找路徑的同時受到了節(jié)點能量消耗的限制,平衡了節(jié)點的能量消耗。

2.3 信息素更新規(guī)則

如果節(jié)點i,j是前向螞蟻k選擇路徑上的相鄰節(jié)點,當每個前向螞蟻到達目的節(jié)點時,它們將通過式(5)、式(6)來調(diào)節(jié)。對前向螞蟻到達目的節(jié)點后立即轉(zhuǎn)化成一個后向螞蟻,并且它將沿著反向信息素表回到源節(jié)點。中間節(jié)點收到后向螞蟻時,將按照式(5)、式(7)更新相鄰節(jié)點信息素強度。

MP-ACA算法改進了MACO算法信息素更新規(guī)則,可以加快搜索路徑的速度,提高網(wǎng)絡數(shù)據(jù)傳輸?shù)膶崟r性,同時更進一步平衡了網(wǎng)絡節(jié)點的能量消耗。

2.4 MP-ACA算法步驟

(1)初始化時,Sink節(jié)點跳數(shù)設置為0,其他節(jié)點跳數(shù)設置為100。Sink節(jié)點在全網(wǎng)范圍內(nèi)廣播跳數(shù)廣播報文,該報文包括數(shù)據(jù)包類型、距Sink節(jié)點跳數(shù)、剩余能量和源地址。該報文初始值為:跳數(shù)為0,源地址為0。中間節(jié)點收到該報文后,保存報文中節(jié)點的地址、跳數(shù)和能量狀態(tài)。

如果收到的報文中跳數(shù)小于節(jié)點自身的跳數(shù),則將自身的跳數(shù)設置為報文中的跳數(shù)加1,并轉(zhuǎn)發(fā)自己新的跳數(shù)信息和能量信息的報文,否則不廣播。節(jié)點在轉(zhuǎn)發(fā)該報文的過程中收集、存儲鄰居節(jié)點相關信息,最終在全網(wǎng)內(nèi)建立了到Sink節(jié)點的跳數(shù)信息。

(2)路徑搜索初始時,賦予每條路徑上相等數(shù)量的初始信息素τ0,本文設置為信息素濃度下限τmin。

(3)路徑搜索開始時,m只前向螞蟻從源節(jié)點S處出發(fā),前向螞蟻所要攜帶的信息有:源節(jié)點ID號、目的節(jié)點ID號、節(jié)點i到節(jié)點j的信息素強度τ(i,j)、經(jīng)過節(jié)點的剩余能量的總和以及當前總跳數(shù)。

(4)位于節(jié)點i的前向螞蟻k,依據(jù)轉(zhuǎn)移規(guī)則從相鄰的下一跳節(jié)點集合中選擇一個節(jié)點,并根據(jù)式(5)、式(6)更新路徑上信息素強度。

(5)當中間節(jié)點j收到來自鄰居節(jié)點的螞蟻節(jié)點時:①更新前向螞蟻搜索包跳數(shù)h(i)=h(i)+1,i∈[1,m]。如果前向螞蟻沒有到達目的節(jié)點,且h

(6)當每個前向螞蟻到達目的節(jié)點時,它們將立即轉(zhuǎn)化成一個后向螞蟻,并且它將沿著反向信息素表回到源節(jié)點。中間節(jié)點收到后向螞蟻數(shù)據(jù)包時,按照式(5)、式(7)將更新相鄰節(jié)點信息素強度,并建立到目的節(jié)點的路由表,路由表是一個三元組包括:目的節(jié)點、下一個節(jié)點、信息素。

(7)后向螞蟻到達源節(jié)點后路由建立完畢。

2.5 網(wǎng)絡的維護

在無線傳感器網(wǎng)絡中,節(jié)點的故障和能量的耗盡都將導致網(wǎng)絡拓撲結(jié)構(gòu)的變化,這使得路由維護顯得十分重要。路由斷路和節(jié)點能量的消耗是路由維護中必須解決的兩個關鍵問題。

(1)路由斷路。

當中間節(jié)點發(fā)現(xiàn)路徑不通或收到路由斷路的消息后,它首先根據(jù)斷路的路徑信息刪除自己對應的路由表條目,然后查詢可能性路由表條目,看是否能找到到達同一目的地的其他路徑。如果有,則根據(jù)路由表中信息素最大的條目作為最優(yōu)的路徑進行通信;

如果沒有到達對應目的地的可選路徑后,即向其他節(jié)點繼續(xù)發(fā)送路由斷路消息。當源節(jié)點在通信完成前收到路由斷路消息后,如果沒有到目的地的其他路徑,則將發(fā)起新的路徑探索過程,直到通信完成。

(2)節(jié)點能量的消耗。

為了不頻繁地重建路由表,節(jié)省能量,MP-ACA算法根據(jù)每個節(jié)電的剩余能量自動更新路由表,這樣就使得節(jié)點的能耗盡可能保持平衡。節(jié)點能量每下降10%,節(jié)點就會向周圍節(jié)點廣播自己的剩余能量,收到廣播的節(jié)點用式(8)更新路由表:

為了分析改進方案的性能,這里選用了以下2個典型參數(shù):(1)接收到數(shù)據(jù)包的平均時延(EndtoEndAverageDelay),單位為s;(2)能量不為零的節(jié)點數(shù)目(NumberofNodes)。

3.1 接收到數(shù)據(jù)包的平均延時

圖1反映了三種算法網(wǎng)絡傳輸數(shù)據(jù)的平均傳輸延時隨時間的變化關系。由圖可知,各算法的時延呈現(xiàn)先降后增的趨勢,主要是由于網(wǎng)絡剛建立時,節(jié)點需要建立路由表,然后時延呈下降趨勢。網(wǎng)絡運行一段時間后,由于網(wǎng)絡中部分節(jié)點死亡,導致路由的重建,致使時延呈上升趨勢。

總的來說,MP-ACA的平均傳輸延時要小于MACO和ACA的平均傳輸延遲,主要是因為在MACO和ACA其路由是通過多次迭代而建立起來的,需要的時間長,從而增加了網(wǎng)絡延時。

3.2 能量不為零的節(jié)點數(shù)目

圖2反映了三種算法在整個網(wǎng)絡時間內(nèi)能量不為零的節(jié)點數(shù)目隨時間的變化關系。由圖可知,節(jié)點一直運行到110s的時候,三種算法下有效的節(jié)點數(shù)目都為總的節(jié)點數(shù)目,但隨著時間的推移,由于ACA算法沒有考慮到節(jié)點剩余能量的情況,造成了某些節(jié)點耗能不均衡而過早的能量耗盡。與MACO算法相比,MP-ACA由于減少了路由過程節(jié)點能量的消耗,性能有了一定的提高。

蟻群算法作為一種新的仿生優(yōu)化算法,具有分布計算、信息正反饋和啟發(fā)式搜索等特點。本文在對現(xiàn)有無線傳感器網(wǎng)絡蟻群改進路由算法的基礎上,改進了現(xiàn)有路由算法路徑搜索方式,很好地權(quán)衡了路由收斂速度與網(wǎng)絡生命周期的相互制約關系。同時將其應用在無線傳感器網(wǎng)絡中進行路由選擇,對于提高無線傳感器網(wǎng)絡的網(wǎng)絡效率、延長網(wǎng)絡的生存周期具有很高的應用價值。

參考文獻

[1]李建中,李金寶,石勝飛.傳感器網(wǎng)絡及其數(shù)據(jù)管理的概念、問題與進展[J].軟件學報,2003,14(10):1717-1727.

[2]劉雯雯,馬銳,許海濱.均衡無線傳感器網(wǎng)絡能耗的AODV改進方案[J].計算機工程,2008,34(22):143-147.

[3]梁華為,陳萬明,李帥,等.一種無線傳感器網(wǎng)絡蟻群優(yōu)化路由算法[J].傳感器技術學報,2007,20(11):2450-2455.

[4]黎劍兵,鄭巍.無線傳感器網(wǎng)絡多種群蟻群優(yōu)化路由算法[J].計算機應用研究,2009,7(26):2686-2690.

[5]GUNESM,SORGESU,BOUAZIZI.IARA-the-ant-colonybasedroutingalgorithmforMANETS[C].InternationalConferenceonParallelProcessingWorkshops(ICPPW’02).2002:79-85.

[6]KASSABALIDISI,El-SHARKAWIMA,MARKSRJ.Swarmintelligenceforroutingincommunicationnetworks[J].GlobalTelecommunications,2001,6(6):3613-3617.

[7]STUTZLET,HOOSHH.Max-Minantsystems[J].FutureGenerationComputerSystems,2000,16(19):889-914.

[8]于斌,孫斌,溫暖,等.NS2與網(wǎng)絡模擬[M].北京:人民郵電出版社,2007.

本站聲明: 本文章由作者或相關機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉
關閉