屈應照,胡曉輝,宗永勝,張榮光
(蘭州交通大學電子與信息工程學院,蘭州730070)
WSN中一種基于數(shù)據(jù)融合的Mobile Agent路徑規(guī)劃方法*
屈應照,胡曉輝*,宗永勝,張榮光
(蘭州交通大學電子與信息工程學院,蘭州730070)
MA(Mobile Agent)技術作為一種分布式中間件的方法,它很適合應用于WSN中自主性的數(shù)據(jù)融合和能量均衡方面。但是現(xiàn)有的一些MA路徑規(guī)劃方法確定的路徑只考慮節(jié)點間的物理距離,此時網絡會出現(xiàn)數(shù)據(jù)負載不均衡、延遲和安全性等一系列問題。針對上述問題,提出一種基于MA協(xié)議的路徑規(guī)劃方法(LDLM),該算法采用K-means聚類算法對網絡分簇,然后由Sink節(jié)點根據(jù)每個簇節(jié)點規(guī)模派發(fā)若干個MA;并且在確定每個MA節(jié)點訪問組時,綜合考慮了節(jié)點采集數(shù)據(jù)量的規(guī)模和MA可用存儲空間。最后,根據(jù)每個MA節(jié)點訪問組,使用LCF算法確定MA對其節(jié)點訪問組的訪問路徑。仿真實驗結果表明:該算法在能量消耗、網絡生命周期、任務工作周期三個方面性能表現(xiàn)優(yōu)于現(xiàn)有的一些算法。
無線傳感器網絡;Mobile Agent;數(shù)據(jù)融合;多路徑規(guī)劃;能量均衡
EEACC:6150P;7230;6210Qdoi:10.3969/j.issn.1004-1699.2016.07.015
無線傳感器網絡WSN(Wireless Sensor Network)由一些大量微型的傳感器節(jié)點組成,這些節(jié)點采集其監(jiān)測區(qū)域的環(huán)境信息,并通過無線通信方式形成一個多跳自組織的網絡系統(tǒng),將采集的數(shù)據(jù)以節(jié)點間協(xié)作的方式傳輸?shù)絽R聚節(jié)點,由匯聚節(jié)點進一步處理并利用Internet、衛(wèi)星等通信方式將最終結果傳輸給遠程用戶終端。網絡中每個節(jié)點既是充當監(jiān)測區(qū)域的信息采集者,同時又有可能是路由轉發(fā)者。WSN網絡結構圖如圖1所示。
無線傳感器網絡帶來了一種基于數(shù)據(jù)收集方法的重要新技術,它的強大功能優(yōu)勢表現(xiàn)在大量節(jié)點的隨機部署和高質量的服務[1]。無線傳感器網絡提供節(jié)點間協(xié)作處理的方式,這種方式允許聯(lián)合多個源節(jié)點采集的數(shù)據(jù)進行集中處理;其中,相鄰節(jié)點間存在一種很普遍的現(xiàn)象即:相鄰節(jié)點間存在著高度的時空相關性。針對這個現(xiàn)象,在數(shù)據(jù)傳輸前可以采用數(shù)據(jù)融合技術,利用相鄰節(jié)點之間由于時空相關性而存在的數(shù)據(jù)冗余,進行網內處理減少節(jié)點之間的數(shù)據(jù)冗余。從而降低網絡中節(jié)點間數(shù)據(jù)傳輸量,節(jié)省了大量網絡資源且明顯提高網絡的感知效能,延長了網絡的生命周期,達到了減小時間延遲的效果。WSN中基于數(shù)據(jù)融合模型的路由協(xié)議研究有:基于簇的協(xié)議[2-3]、基于鏈式的協(xié)議[2]、基于生成樹的協(xié)議[2]和基于Mobile Agent協(xié)議[2]。其目標都是建立一種底層的拓撲結構,以便有效利用網絡節(jié)點的能量資源[4]。
圖1 無線傳感器網絡結構圖
Mobile Agent是一段可以在網絡節(jié)點間自主運行的程序代碼,它裝載著用戶指定的任務,在每個被訪問的節(jié)點進行局部的數(shù)據(jù)收集、融合處理;以這種方式遍歷網絡相關節(jié)點完成指定任務,攜帶任務結果返回匯聚節(jié)點,匯聚節(jié)點將最終結果進行處理并反饋給用戶。MA計算模型如圖2所示。MA在WSN中進行數(shù)據(jù)收集和融合操作時,對其所需訪問相關節(jié)點,需要根據(jù)一定原則規(guī)劃一個訪問序列,即:需要對MA訪問節(jié)點的路徑進行一個規(guī)劃。因為MA訪問的路徑很大程度上會影響整個網絡的能量消耗、網絡負載均衡問題及數(shù)據(jù)融合操作的開銷。為了降低MA訪問路徑對網絡的影響和開銷問題,一些啟發(fā)式思想方法已經被研究者提出并應用在WSN中。這些啟發(fā)式思想方法對MA規(guī)劃的訪問路徑,既有動態(tài)確定MA路由中下一個要訪問的節(jié)點的路徑規(guī)劃方法;也有靜態(tài)確定MA路由問題的路徑規(guī)劃方法。其中,動態(tài)確定MA訪問路徑的方法比較適合應用在一些移動對象的路徑蹤跡在初始狀態(tài)下是未知的,例如:目標追蹤、分類器應用等。靜態(tài)確定MA訪問路徑的方法比較適合應用在周期性采集其監(jiān)測物理環(huán)境信息(比如:溫度、濕度等)并傳輸給匯聚節(jié)點,例如:在數(shù)據(jù)監(jiān)測方面的應用。
圖2 Mobile Agent協(xié)議計算模型
在對MA路徑規(guī)劃的方法中,無論是動態(tài)規(guī)劃方法還是靜態(tài)規(guī)劃方法,都有其優(yōu)劣。動態(tài)路徑規(guī)劃方法對訪問途中的MA,可以在改變其遷移路徑時可能發(fā)生的錯誤做出實時的反應。但是在動態(tài)路徑規(guī)劃方法中的每個節(jié)點處,動態(tài)確定MA下一個將要訪問的節(jié)點時需要較多的決策時間;它同時還會消耗更多的能量,并且對MA的容量需求更大(因為MA智能性越高,其對MA的功能需求就越多)。另外,動態(tài)規(guī)劃方法還需要一個有效的路由協(xié)議,以便MA不僅可以動態(tài)確定其下一個將要訪問節(jié)點還可以確定其返回到匯聚節(jié)點的路徑;這些問題對于靜態(tài)路徑規(guī)劃的方法都是不需要的。因為在靜態(tài)路徑規(guī)劃方法中,每個MA都是使用預先確定的路徑;這些路徑都是由派發(fā)MA的Sink節(jié)點在派發(fā)MA之前,根據(jù)網絡狀況和先驗知識條件計算而確定的。
靜態(tài)路徑規(guī)劃的方法可以分為2類:①對單個MA路徑規(guī)劃SIP(Single Mobile Agent Itinerary Planning)[5];②對多個MA路徑規(guī)劃MIP(Multi-Mobile Agents Itinerary Planning)[5],這兩種方法計算模型如圖2所示。這兩種方法都是派發(fā)一個MA或者同時派發(fā)多個MA到WSN中,每個MA都會被分配網絡中節(jié)點集合的一個子集;MA對其分配節(jié)點子集進行數(shù)據(jù)收集、融合和處理。SIP在小型WSN網絡條件下,性能表現(xiàn)出令人滿意的成果;但是隨著WSN中節(jié)點數(shù)量的增加,SIP的性能狀況開始惡化。這是由于隨著網絡節(jié)點數(shù)量的增加,MA在其分配的節(jié)點子集中進行收集和融合源節(jié)點的數(shù)據(jù)時,MA的往返時延和能量開銷也隨著網絡規(guī)模增加而急劇上升[2]。同時,隨著網絡節(jié)點數(shù)量的增加,MA在收集數(shù)據(jù)的規(guī)模也逐漸增加,進而增加網絡的帶寬資源消耗和節(jié)點的能量開銷。此外,SIP方法還可能會產生其他隱患問題,例如:MA在幾個節(jié)點之間的遷移時,會發(fā)生MA丟失現(xiàn)象[6-7]。然而MIP可以有效地規(guī)避上述問題,MIP通過派發(fā)多個MA到網絡中并行收集、融合源節(jié)點的數(shù)據(jù);由于每個MA被分配一個節(jié)點數(shù)量較小的節(jié)點子集,因而在一定程度上高效地緩解了SIP方法在網絡規(guī)模增大時產生的一系列隱患問題。
正如本文引言部分描述,MIP在一定程度上性能表現(xiàn)要優(yōu)于SIP方法;因而,基于MIP的思想方法近年以來吸引眾多研究者的研究興趣,并且產生了以一系列比較經典的研究成果。文獻[6]提出一種基于樹的分支結構路徑規(guī)劃算法(CBID),此算法在包含完成用戶指定任務所必需相關網絡節(jié)點的條件下,使得網絡的總開銷最小。該算法在減少網絡總體能量開銷和網絡延遲方面有著顯著作用;但是隨著網絡規(guī)模的增大,樹中會產生越來越多的分支,這些數(shù)量眾多分支會影響該算法的性能。文獻[7]提出了VCL(The Visiting Central Location)算法是首先是通過節(jié)點間影響因子確定訪問中心點,然后根據(jù)訪問中心點將網絡中所有的位于特定距離的節(jié)點劃分同一個簇,重復執(zhí)行這個過程直到每個節(jié)點都被劃分到一個簇中。然后由Sink節(jié)點給每個簇派發(fā)一個MA,通過使用SIP方法中算法確定MA在各自分配的簇中節(jié)點的訪問路徑。但是,在實際網絡環(huán)境中由于應用環(huán)境條件的限制,節(jié)點通常是無規(guī)律性分布;這種情況下簇的劃分將大幅度受影響,進而影響算法效率。在文獻[8]中描述了 BST(Balanced Minimum Spanning Tree)算法,該算法首先使用普里姆算法產生一棵根植于匯聚節(jié)點的生成樹。在這棵生成樹中所有擁有單分支的節(jié)點被劃分為同一個簇。然后給每個簇派發(fā)一個MA,并使用SIP方法中的算法產生一條MA訪問簇中節(jié)點的路徑。文獻[9]NOID(The Near-Optimal Itinerary Design)算法主要目的是確定網絡中完成用戶指定任務所需MA數(shù)量的最優(yōu)值,同時該最優(yōu)值可以最小化網絡中數(shù)據(jù)融合操作的開銷;但是此算法面臨著較慢的計算速率和高復雜度的計算過程。文獻[2]提出了一種TBID(The Tree-Based Itinerary Design)算法,它是對文獻[9]進行改進而產生的一個啟發(fā)式算法,它采用貪婪式算法思想選擇距離最小的節(jié)點形成一個二叉樹。TBID算法不僅確定了網絡中MA數(shù)量的近優(yōu)值,使得網絡融合開銷最?。煌瑫r為網絡中所有的MA規(guī)劃一條網絡開銷近優(yōu)的路徑。
MIP方法中現(xiàn)有的算法和研究大部分都是基于節(jié)點的物理距離作為MA路徑規(guī)劃的唯一參考因素。在現(xiàn)實環(huán)境中,由于網絡節(jié)點的無規(guī)律分布,當將網絡節(jié)點劃分為簇時,各個簇的節(jié)點規(guī)模也不統(tǒng)一,導致各個簇產生的數(shù)據(jù)量存在差異。進而導致各個簇的MA攜帶的數(shù)據(jù)量不同,最終引起網絡上數(shù)據(jù)負載和能量不均衡。因此,對MA之間的數(shù)據(jù)規(guī)模差異進行調節(jié),可以優(yōu)化用戶任務在網絡上的工作周期,有效地確保網絡能量和數(shù)據(jù)負載均衡,并且可以降低網絡的丟包率。
基于上述問題,本文在對MA進行路徑規(guī)劃時不僅考慮節(jié)點之間的物理距離;同時,對網絡中簇的劃分方式以及計算、確定網絡中MA數(shù)量的方法進行改進。從而,在一定程度上可以有效地解決網絡數(shù)據(jù)負載不均衡、延遲和安全性等方面的問題;并且減少任務工作周期,節(jié)約了網絡的能量消耗,延長了網絡生命周期。
本文提出的方法屬于靜態(tài)規(guī)劃方法,即:MA的訪問路徑由派發(fā)MA的Sink節(jié)點在派發(fā)之前,根據(jù)網絡狀況和先驗知識條件規(guī)劃和確定的一條訪問路徑。由于靜態(tài)路徑規(guī)劃方法中MIP方法的性能在一定程度要上優(yōu)于SIP;所以,本文提出的方法同屬于MIP方法思想范疇。
本文提出路徑規(guī)劃方法,主要可以分為以下3個部分:①基于節(jié)點物理位置,將整個網絡劃分為幾個子區(qū)域。這個階段最終結果就是產生一個關于節(jié)點子區(qū)域的集合。②確定整個網絡中每個子區(qū)域所需MA的數(shù)量;并且結合子區(qū)域中每個源節(jié)點采集的數(shù)據(jù)量和MA自身可用存儲空間的規(guī)模,從而計算出子區(qū)域中每個MA需要訪問的一組節(jié)點。③根據(jù)一定算法確定MA對其組內節(jié)點的訪問序列,即:規(guī)劃MA對其組內節(jié)點的訪問路徑。
2.1網絡的劃分
本文假定WSN網絡節(jié)點具有定位功能和剩余能量感知功能,每個節(jié)點都可以發(fā)送自己的坐標給Sink節(jié)點;因而,Sink節(jié)點根據(jù)這些坐標數(shù)據(jù)計算整個網絡節(jié)點的分布情況。根據(jù)WSN分簇路由算法的特點和K-Means算法[10-11]的優(yōu)勢,本文采用K-Means算法將整個網絡劃分為K個簇[11]。K-Means算法對大數(shù)據(jù)集有著較高效率并且是可伸縮性的,因而,它經常被應用在WSN分簇方面。分簇思想在WSN的節(jié)能和穩(wěn)定性方面的應用有著重要意義[12](為了概念的統(tǒng)一,本文把網絡中節(jié)點劃分的子區(qū)域統(tǒng)稱為簇)。在分簇思想中,簇中的簇頭節(jié)點負責收集處理其簇內節(jié)點采集的數(shù)據(jù),并將最終結果間接或直接發(fā)送給Sink節(jié)點;但是,本文是根據(jù)簇的規(guī)模大小給每個簇分配若干個MA,這些MA負責收集處理其簇內節(jié)點采集的數(shù)據(jù)。本文引進K-Means算法用于對網絡進行簇的劃分,即:確定網絡中所有MA的工作區(qū)域。
本文采用K-Means聚類算法,在網絡初始化時由Sink節(jié)點對網絡進行集中式固定分簇;簇一旦形成后,在整個網絡生命周期內簇的結構不再改變。在數(shù)據(jù)收集第一輪時簇內具有物理位置和能量優(yōu)勢的節(jié)點成為該簇的簇頭節(jié)點。在后續(xù)每輪數(shù)據(jù)收集中根據(jù)閥值計算和判斷是否需要進行簇頭更新工作;有些輪次需要進行簇頭更新,有些輪次不需要進行簇頭更新;如需進行簇頭更新,則由當前簇頭節(jié)點確定下一個簇頭節(jié)點。因而,可以節(jié)約在每輪進行非必須性的簇頭更新工作帶來網絡開銷、降低算法復雜度和網絡能耗開銷。本文分簇思想執(zhí)行工作流程示意圖,如圖3所示。
圖3 本文分簇思想執(zhí)行流程示意圖
2.1.1聚類分簇
圖4 K-Means算法劃分簇的過程
2.1.2簇頭選取
分簇工作完成后,Sink節(jié)點將分簇信息分發(fā)給網絡中的節(jié)點,信息包括簇ID、簇內節(jié)點距離Sink節(jié)點最大和最小的距離值。收到分簇信息后,簇內節(jié)點開始根據(jù)自身能量和物理位置競爭簇頭節(jié)點。因為物理位置決定節(jié)點與Sink節(jié)點的通信距離,而通信距離與網絡能量消耗密切相關;所以簇頭節(jié)點必定是簇內距離Sink節(jié)點最近且剩余能量最多的節(jié)點。綜上所述,并根據(jù)文獻[13-14]研究論證,本文節(jié)點采用公式(3)計算其延遲時間T,
其中,α∈(0,1)為系數(shù)因子;D為當前節(jié)點與Sink節(jié)點的距離;Dmin為當前簇內節(jié)點與Sink節(jié)點最小的距離;Dmax為當前簇內節(jié)點與Sink節(jié)點最大的距離;E1為當前節(jié)點的剩余能量值;E0為網絡中節(jié)點的初始能量值。
通過式(3)距離Sink節(jié)點最近且剩余能量最大的節(jié)點成為簇頭節(jié)點,即:節(jié)點的延遲時間T最小,因此可以優(yōu)先在網絡中廣播自己的競爭簇頭節(jié)點消息,簇內第一個在網絡上廣播其競爭簇頭消息的節(jié)點則成為簇頭節(jié)點。當簇內節(jié)點收到簇內其他節(jié)點優(yōu)先發(fā)送來競選消息時,則放棄本輪其競選簇頭的機會。簇頭節(jié)點廣播消息包括節(jié)點ID和其剩余能量值。
2.1.3數(shù)據(jù)量信息采集
在網絡簇頭節(jié)點確定后,簇內各個節(jié)點分別發(fā)送消息加入該簇,消息包括自己剩余能量值、節(jié)點ID和節(jié)點距離Sink節(jié)點的距離。簇頭節(jié)點收到簇內節(jié)點發(fā)送的加入消息后,根據(jù)簇的規(guī)模采用TDMA方式給每個節(jié)點分配時隙;各個節(jié)點在對應的時隙中將自身采集數(shù)據(jù)量描述信息(而非采集的數(shù)據(jù))發(fā)送給簇頭節(jié)點;節(jié)點在非本身對應時隙則保持睡眠狀態(tài)以節(jié)約能量。簇頭節(jié)點將簇內節(jié)點發(fā)送的數(shù)據(jù)采集量描述信息以直接或間接方式轉發(fā)給Sink節(jié)點;Sink節(jié)點根據(jù)此描述信息,確定給每個簇派發(fā)MA的數(shù)量。因此,各個簇節(jié)點采集數(shù)據(jù)量大小對于計算給每個簇派發(fā)MA的數(shù)量和確定每個MA所需訪問的節(jié)點組都至關重要(關于本部分內容詳見2.2節(jié)LDLM算法描述)。
2.1.4簇頭調整
在數(shù)據(jù)量信息收集每輪末尾,節(jié)點發(fā)送自身剩余能量值給簇頭。簇頭節(jié)點更新簇內節(jié)點剩余能量值,并采用公式(4)計算簇內節(jié)點參量值
其中,Ei′為節(jié)點i的剩余能量值,Di為節(jié)點i與Sink節(jié)點的距離。
簇頭節(jié)點選擇參量值最大的節(jié)點通過公式(5)進行比較,
如果式(5)成立,則節(jié)點j與當前簇頭節(jié)點交換TDMA時隙信息,并廣播消息成為新簇首節(jié)點;如果式(5)不成立,則不需要進行簇首更新工作。在每輪末尾都通過閥值計算以確定是否需要進行簇頭調整,以減少非必需性的更新操作開銷。
2.2LDLM算法描述
對于確定簇中MA的數(shù)量和MA的節(jié)點訪問組的問題,本文提出的方法是:對于簇內數(shù)據(jù)采集量最大的節(jié)點優(yōu)先分配到擁有可用空間最大的MA的訪問組中,即:LDLM(The Larger Data size in Larger Memory),簡稱為LDLM算法;從而可以有效地確保網絡MA之間數(shù)據(jù)負載均衡。
LDLM算法基本思想如下:在完成簇的劃分后,此時網絡擁有包含所有網絡節(jié)點的k個簇,這些簇規(guī)模大小不必相等。設簇含有m個源節(jié)點,每個源節(jié)點產生初始數(shù)據(jù)量為,MA的可用存儲空間大小為MMA(初始時所有MA的可用空間大小是相等的);則該簇產生的初始數(shù)據(jù)量DS(j)和每個簇所需MA的數(shù)量NbMA,可通過式(6)、式(7)計算得到:
并且,NbMA的值會在算法的執(zhí)行過程中逐漸增加;因為如果在算法執(zhí)行的某個時刻,對于簇中當前所有MA的剩余可用空間,無法將當前簇中數(shù)據(jù)采集量最大的節(jié)點分配給任何一個MA;此時需要Sink節(jié)點給該簇再次派發(fā)一個MA,以確保簇中MA能順利地完成對簇中所有初始數(shù)據(jù)的收集和處理。本文LDLM算法思想提出并采用的MA計算模型如圖5所示。
圖5 LDLM算法采用的MA計算模型
為了更好地描述和說明LDLM算法,本文給出關于LDLM算法的一個簡單示例,如圖6所示。
圖6 LDLM算法的一個簡單的示例
LDLM算法具體實現(xiàn)步驟如表1所示。
表1 LDLM算法的具體實現(xiàn)步驟
2.3確定MA的訪問路徑
在本文的2.1節(jié)、2.2節(jié)部分完成了WSN網絡節(jié)點區(qū)域到簇的劃分,并且確定了每個簇中所需MA的數(shù)量和每個MA完成工作任務所需訪問的一組節(jié)點。接下來,本部分將根據(jù)每個MA節(jié)點訪問組,確定MA對其節(jié)點訪問組的訪問路徑。MA訪問路徑確定之后,MA根據(jù)其訪問路徑便可以開始工作,完成Sink節(jié)點分配的任務,并攜帶最終結果返回到Sink節(jié)點。
在本文LDLM算法中確定MA對其節(jié)點訪問組的訪問路徑問題,可以看作是SIP問題;所以,此時只需采用SIP方法中算法便可確定MA的訪問路徑。本文在這里采用SIP方法中LCF(Local Closest First)算法[5,15],LCF算法就是將距離當前節(jié)點距離最近的節(jié)點,選為MA下一個將要訪問的節(jié)點;重復此過程,直到MA節(jié)點訪問組中的節(jié)點都包含在此訪問路徑上,即:這條訪問路徑起點和終點都是Sink節(jié)點。此時MA對其節(jié)點訪問組的訪問路徑便形成了。
3.1仿真
本文采用CC2430無線模塊模型在TinyOS的TOSSIM平臺,對LDLM算法、LEACH算法[3]和VCL算法[7]進行仿真,并在能量消耗、網絡生命周期和任務工作周期方面對它們進行分析和比較。雖然LEACH算法并不屬于基于 MA協(xié)議范疇,但LEACH算法是基于簇協(xié)議的范疇,而基于簇協(xié)議在WSN數(shù)據(jù)收集、融合和能耗均衡方面問題也是一種很重要思想方法。鑒于本算法和LEACH算法在目標和策略上的相似性,所以將其作為參考和比較對象。VCL算法作為MIP思想方法出現(xiàn)早期產生的算法,較好地體現(xiàn)MIP思想方法優(yōu)越性。而本文提出的LDLM算法同樣屬于MIP方法,為了更好評估LDLM算法的性能,所以將VCL算法也納入實驗進行參考和比較。
TOSSIM是TinyOS[16]操作系統(tǒng)自帶仿真平臺,它可以支持大規(guī)模的網絡仿真[17-18]。TinyOS是由美國加州大學伯克利分校針對WSN研發(fā)一套具有輕量級線程技術、主動消息通信模式、組件化編程、硬件抽象層、事件驅動模式等特性的操作系統(tǒng)。
節(jié)點隨機部署在200m×200m的區(qū)域,Sink節(jié)點部署在網絡區(qū)域的中心位置。假設實驗中無線傳感器網絡具有如下功能:①節(jié)點具有定位功能和剩余能量感知功能;②節(jié)點部署以后不再發(fā)生移動;③每個節(jié)點都有唯一的標識符;④所有節(jié)點都有相同的初始電池能量;⑤網絡中傳輸?shù)乃袉蝹€數(shù)據(jù)包的大小是相同。
本實驗中我們把路徑上傳輸能耗看作是節(jié)點間在發(fā)送和接收MA時產生的能耗,因為在WSN中節(jié)點間傳輸1 bit數(shù)據(jù)的能耗遠遠大于處理該數(shù)據(jù)的能耗,所以只計算節(jié)點間通信傳輸消耗的能量。第j簇內,MA在節(jié)點a和節(jié)點b之間遷移時產生傳輸能耗采用式(8)~式(10)[3]計算得到:
其中,k表示MA裝載數(shù)據(jù)包的大小,單位為bit;Eelec表示節(jié)點在發(fā)送或接收電路產生的能耗。εamp表示節(jié)點發(fā)送中繼器的信噪比;dab表示節(jié)點間的傳輸距離。
本實驗使用的參數(shù)[7,9]如表2所示。
表2 實驗參數(shù)
在基于TinyOS仿真實驗中,MA在TinyOS中實現(xiàn)方式及工作原理是基于TinyOS主動通信模型,將MA的代碼空間和數(shù)據(jù)空間區(qū)分傳輸[19]。在LDLM算法中,MA在遍歷其訪問路徑時并不會立即對訪問節(jié)點的數(shù)據(jù)進行收集和處理,而是在MA到達其訪問路徑中距離Sink節(jié)點最遠的源節(jié)點(即:路徑的最外層節(jié)點)后,并且在返回到Sink節(jié)點的途中,此時開始進行節(jié)點數(shù)據(jù)的收集和融合處理。這樣可以減緩MA在網絡中遷移時數(shù)據(jù)負載和能量開銷。圖7展示了LDLM算法在網絡節(jié)點被指定分成4個簇后,各個簇MA產生訪問路徑的情況。其中,MA2,MA3屬于同一個簇,因為該簇的源節(jié)點數(shù)據(jù)采集量比較大,在LDLM算法執(zhí)行條件下,Sink節(jié)點便給該簇分派了兩個MA完成該簇的網絡任務。
圖7 LDLM算法產生網絡拓撲圖的示例
3.2實驗結果分析
為了評估本文提出LDLM算法的性能,在仿真過程中,本文在以下3個方面與LEACH算法、VCL算法進行了比較。即:
①能量消耗:在WSN中能量消耗情況是評估算法重要的性能指標。圖8是3種算法在含有200個節(jié)點情況下,節(jié)點消耗的總能量與采集周期的變化關系。
圖8 數(shù)據(jù)采集輪數(shù)對網絡總能量消耗的影響
由圖8可以看出,LEACH算法的能耗明顯高于VCL算法、LDLM算法,而后兩者能耗差距相對較小。這是由于基于簇協(xié)議的LEACH算法簇頭分布過于集中在局部區(qū)域,造成部分節(jié)點與簇頭的數(shù)據(jù)傳輸能耗增大,同時引起簇頭的能耗過高;而LDLM、VCL算法采用MA協(xié)議進行數(shù)據(jù)采集。在VCL算法中,各個簇被Sink節(jié)點僅派發(fā)一個MA進行數(shù)據(jù)采集;由于節(jié)點無規(guī)律分布,造成各個簇的規(guī)模不均勻,進而導致MA數(shù)據(jù)負載不均衡;同時簇的規(guī)模越大,造成MA需要消耗更多的能量和時間返回到Sink節(jié)點。LDLM算法在節(jié)點無規(guī)律分布下,根據(jù)各個簇的規(guī)模給其派發(fā)若干個MA有效地均衡網絡中MA的數(shù)據(jù)負載;從而減少了網絡總能量消耗,同時網絡性能也得到改善。
②網絡生命周期:圖9表示的是網絡剩余存活節(jié)點數(shù)量與數(shù)據(jù)采集周期的變化關系。
圖9 節(jié)點數(shù)量對網絡生命周期影響
由圖9可以看出,隨著數(shù)據(jù)采集時間的增長,三種算法執(zhí)行過程中均出現(xiàn)節(jié)點死亡;其中,LDLM算法的生命周期最長。這是由于LDLM算法根據(jù)節(jié)點的物理位置和各個簇中節(jié)點數(shù)據(jù)采集量,合理地確定和規(guī)劃MA的節(jié)點訪問組及對其節(jié)點訪問組的訪問路徑,較好地實現(xiàn)了網絡上MA的數(shù)據(jù)負載均衡;從而使網絡上能量消耗比較均勻地分布在所有網絡節(jié)點中,避免網絡局部區(qū)域節(jié)點因能量消耗過度而超前失效,因而可以有效地延長網絡的生命周期。
③任務工作周期:圖10反映的是數(shù)據(jù)采集任務完成時間隨著網絡節(jié)點數(shù)量變化而變化的關系。
圖10 節(jié)點數(shù)量對任務執(zhí)行周期的影響
在基于MA協(xié)議中,指MA由Sink節(jié)點派發(fā)開始至MA返回到Sink節(jié)點時結束所耗費的時間。由于LDLM算法是基于MIP的計算模式,所有MA并行工作,大幅度提高數(shù)據(jù)收集效率;并且MA只在移動時才占用網絡,大大節(jié)省了網絡帶寬和能量資源。VCL算法通過節(jié)點間影響因子來確定節(jié)點的訪問中心點進而對網絡進行劃分,由于節(jié)點隨機部署導致VCL算法的影響因子和訪問半徑很大程度上影響算法性能,正如圖10所示,LDLM網絡延遲最小。而在LEACH算法中,簇頭負責收集其簇內節(jié)點的數(shù)據(jù)并根據(jù)需要進行融合處理,然后將處理結果采用單跳方式發(fā)送給Sink節(jié)點;這種情況下,當網絡源節(jié)點產生的數(shù)據(jù)量很大時,LEACH采用TDMA方式與各節(jié)點通信明顯具有很大的網絡延遲并且數(shù)據(jù)收集效率也大大降低了。從圖10可以看到,LEACH算法在隨著節(jié)點數(shù)量的增加,任務工作周期受影響程度逐漸增大。
在基于MA協(xié)議中,MA的訪問路徑對于網絡資源開銷有著很大的影響。基于MIP方法明顯提高了WSN性能,尤其是在節(jié)約能量、均衡網絡負載和數(shù)據(jù)收集方面具有顯著效益。但是現(xiàn)有基于MIP方法的一些算法在對MA路徑進行規(guī)劃時,只考慮節(jié)點間的距離,這種方式下產生了很大網絡數(shù)據(jù)負載不均衡等一系列問題。針對這些問題,本文基于MIP思想方法提出LDLM算法,該算法綜合考慮網絡劃分后各個簇的規(guī)模,并且提出一種新的方式計算和確定各個簇所需MA數(shù)量以及每個MA的節(jié)點訪問組及MA在組內的訪問路徑。通過在TinyOS的TOSSIM平臺仿真實驗,并且與LEACH算法、VCL算法進行比較,實驗結果表明LDLM算法的性能在能量消耗、網絡生命周期和任務工作周期等方面表現(xiàn)出一定優(yōu)越性。
[1] Chen M,Gonzalez Valenzuela S,Leung V.Directional Source Grouping for Multi-Agent Itinerary Planning in Wireless Sensor Networks[C]//Information and Communication Technology Convergence(ICTC),2010 International Conference on.IEEE,2010:207-212.
[2] Konstantopoulos C,Mpitziopoulos A,Gavalas D,et al.Effective Determination of Mobile Agent Itineraries for Data Aggregation on Sensor Networks[J].Knowledge and Data Engineering,IEEE Transactions on,2010,22(12):1679-1693.
[3] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//System Sciences,2000.Proceedings of the 33rd Annual Hawaii International Conference on.IEEE,2000,10(l):2.
[4] 張美燕,蔡文郁.融合K均值分簇MST路由的無線傳感網壓縮采樣技術[J].傳感技術學報,2015,28(9):1402-1407.
[5] Qi H,Wang F.Optimal Itinerary Analysis for Mobile Agents in Ad Hoc Wireless Sensor Networks[J].Proceedings of the IEEE,2001:147-153.
[6] Mpitziopoulos A,Gavalas D,Konstantopoulos C,et al.CBID:a Scalable Method for Distributed Data Aggregation in WSNs[J]. International Journal of Distributed Sensor Networks,2010,5(4):1-13.
[7] Chen M,Gonzalez S,Zhang Y,et al.Multi-Agent Itinerary Planning for Wireless Sensor Networks[J].Quality of Service in Heterogeneous Networks,2009:584-597.
[8] Chen M,Cai W,Gonzalez S,et al.Balanced Itinerary Planning for Multiple Mobile Agents in Wireless Sensor Networks[M]//Ad Hoc Networks.Springer Berlin Heidelberg,2010:416-428.
[9] Gavalas D,Mpitziopoulos A,Pantziou G,et al.an Approach for Near-Optimal Distributed Data Fusion in Wireless Sensor Networks[J].Wireless Networks,2010,16(5):1407-1425.
[10]Peng W,Edwards D J.K-Means Like Minimum Mean Distance Algorithm for Wireless Sensor Networks[C]//Computer Engineering and Technology(ICCET),2010 2nd International Conference on. IEEE,2010(1):120-124.
[11]Zhou J,Zhang Y,Jiang Y,et al.A Distributed K-Means Clustering Algorithm in Wireless Sensor Networks[C]//Informative and Cybernetics for Computational Social Systems(ICCSS),2015 International Conference on.IEEE,2015:26-30.
[12]Wang G,Cho G.Securing Cluster Formation and Cluster Head Elections in Wireless Sensor Networks[J].International Journal of Communication Networks and Information Security(IJCNIS),2014,6(1):70-88.
[13]張海燕,劉虹.基于K-Means聚類的WSN能耗均衡路由算法[J].傳感技術學報,2011,24(11):1639-1643.
[14]張雅瓊.基于K-Means的無線傳感網均勻分簇路由算法研究[J].控制工程,2015,22(6):1181-1185.
[15]Wu Q,Rao N S V,Barhen J,et al.On Cmputing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks[J].Knowledge and Data Engineering,IEEE Transactions on,2004,16(6):740-753.
[16]http://www.tinyos.net/.
[17]李鷗.TinyOS實用編程[M].機械工業(yè)出版社,2013.
[18]潘浩董齊芬張貴軍,等.無線傳感器網絡操作系統(tǒng)TinyOS[M].北京:清華大學出版社,2011.
[19]林華杰,史浩山.基于無線傳感器網絡移動代理變種在TinyOS中的實現(xiàn)[J].傳感技術學報,2008,28(10):2324-2327.
屈應照(1989-),男,蘭州交通大學電子信息與工程學院碩士研究生。研究方向為智能信息處理,智能分布式系統(tǒng),無線傳感器網絡,523818641@qq.com;
胡曉輝(1963-),男,蘭州交通大學電子與信息工程學院教授,博士,研究方向為智能分布式系統(tǒng)、智能計算和智能信息處理等。先后參與國家自然科學基金、省自然科學基金、省科技攻關項目、北京鐵路局科技攻關項目和省教育廳碩士生導師項目;其中已完成的項目中有4項獲得省部級科技獎勵,發(fā)表相關學術論文40余篇,其中EI檢索6篇,hxh_6302@163.com;
宗永勝(1990-),男,蘭州交通大學電子信息與工程學院碩士研究生。研究方向為智能信息處理,智能分布式系統(tǒng),787673854@qq.com。
An Approach Itinerary Planning for Mobile Agent Based on Data Fusion in WSN*
QU Yingzhao1,HU Xiaohui1*,ZONG Yongsheng1,ZHANG Rongguang1
(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)
As a distributed middleware,Mobile Agent technology is suitable for autonomic data fusion and energy balance in wireless sensor networks.Several heuristic methods have been widely applied to the way the Itinerary planning of Mobile Agent,but some of these methods just consider the geographical distance among nodes as the unique factor when planning the Itinerary.There will cause the emergence of the data load unbalancing,large delay and security problems when WSN uses these methods.For tackling above problems,the Larger Data size in the Larger Memory(LDLM)algorithm is proposed.In this proposed scheme,we don't only consider the geographical distance among nodes but take into account the data size from source nodes.Extensive simulation experiments show that the LDLM algorithm behaves better performance than other approaches on these three aspects consumption energy,life cycle and task duration.
WSN;Mobile Agent;Data Fusion;Multi-Itinerary Planning;Energy Balance
TP391
A
1004-1699(2016)07-1032-10
項目來源:國家自然科學基金項目(61163009);甘肅省科技計劃項目(144NKCA040)
2016-01-04修改日期:2016-03-08