黃光群，孫 暉，路 揚，詹亞曙

(浙江大學 電氣工程學院，浙江 杭州310027)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是由具有能夠感知監(jiān)測區(qū)域感興趣信息能力、無線數(shù)據(jù)傳輸能力和處理信息能力的傳感器節(jié)點組成的自組織網(wǎng)絡(luò)［1］。如何提高節(jié)點能量的利用率成為WSNs 路由研究的熱點問題［2］。傳統(tǒng)的客戶/服務器(C/S)模式在WSNs 中沒有利用數(shù)據(jù)的相關(guān)性進行融合，容易造成較高能耗［3］，而且，若干源節(jié)點與基站進行數(shù)據(jù)交換時對于流量寬帶較窄的WSNs 容易造成路徑損耗［4］。

針對上述問題，文獻［5］提出基于移動代理(mobile agent，MA)的LCF 和GCF 算法，其能壓縮數(shù)據(jù)，減少網(wǎng)絡(luò)寬帶的需求，但該算法通過節(jié)點地理位置決定MA 路線，網(wǎng)絡(luò)分布復雜時其性能很差。文獻［6］提出DSG—MIP 算法，將網(wǎng)絡(luò)劃分為若干區(qū)域，派出若干MA 訪問相應區(qū)域，相比單一MA，具有更好的性能，但未考慮節(jié)點剩余能量。

上述算法研究主要應用于平面路由模式下，本文受到DSG—MIP 算法的啟示，在三維胞元模型［7］的基礎(chǔ)上提出了MA 雙向并行(3D—BPMA)路由算法。該算法根據(jù)三維胞元系統(tǒng)的特點，將整個三維空間按縱向和橫向分別劃分為不同的集合，不同集合間通過并行克隆的方式產(chǎn)生MA，提高了整個網(wǎng)絡(luò)的訪問速度。

1 相關(guān)模型

1.1 三維胞元空間模型

以參考點O 為坐標原點建立三維坐標系如圖1 所示［7］，其中，節(jié)點i 的坐標為(xi，yi，zi)，其所在的胞元坐標為(XI，YI，ZI)，Rmax是節(jié)點最大通信半徑，在三維胞元空間內(nèi)規(guī)定胞子只能與本胞元內(nèi)節(jié)點進行通信，不能與鄰居胞元內(nèi)的節(jié)點通信。胞父節(jié)點是本胞元內(nèi)按照自適應選舉選擇出來的，其負責相鄰胞元的通信。

圖1 三維胞元空間模型Fig 1 3D cell space model

1.2 能耗模型與數(shù)據(jù)融合模型

本文采用文獻［8］中的能耗模型，當傳輸g bit 時

其中，lij為傳輸節(jié)點i 和接收節(jié)點j 之間的距離，Eelec為與無線傳輸或者接收有關(guān)的常數(shù)，εamp為與信號衰減有關(guān)的常數(shù)，γ 與當前的阻力有關(guān)，本文取γ=2。

本文采用文獻［9］的數(shù)據(jù)融合模型，訪問第k 個節(jié)點時MA 的表達式如下

其中，r 為數(shù)據(jù)壓縮率，ld為原始感應數(shù)據(jù)大小，ρ(0≤ρ ＜1)為數(shù)據(jù)融合率為訪問完第k 個節(jié)點后MA 的大小為開始時由基站發(fā)出MA 的大小。

1.3 單層系統(tǒng)模型

在三維胞元模型中以胞元長度d 為單位長度，在Z 坐標軸方向上分解出若干單層系統(tǒng)，如圖2 所示。單層系統(tǒng)模型(single-layer system model，SSM)增加了以下屬性:

1)路由器(Router):每個單層系統(tǒng)含有唯一路由器，其負責建立所在層的網(wǎng)絡(luò)和相鄰單層系統(tǒng)之間的通信，其一般位于本層的中心，且自身能量較大。

2)層數(shù)(FloorNum):基站的胞元坐標為(XB，YB，ZB)，路由器的胞元坐標為(XR，YR，ZR)，定義基站所在的層數(shù)為第0 層，路由器所在的層數(shù)為FloorNum=ZR－ZB。

3)最大跳數(shù)(maxHop): maxHop 為Router 與本層邊緣胞父通信所需的最大跳數(shù)，即maxHop=max［(XJ－XR)，(YJ－YR)，(ZJ－ZR)］，圖3 中，單層系統(tǒng)maxHop=3。

4)環(huán)形集合(RingSet):如果將到達路由器跳數(shù)相同的胞父節(jié)點視作一個集合，單層系統(tǒng)模型被分割成環(huán)形集合，RingSetK(K∈N)為該層的第K 個環(huán)形集合，其中路由器所在的集合是RingSet0。如圖3，F(xiàn)1，F(xiàn)2與F3是本層內(nèi)靠近原點的胞父，其分別所屬環(huán)形集合RingSet1，RingSet2，Ring-Set3。

1.4 MA 的數(shù)據(jù)包格式

本文定義MA 的數(shù)據(jù)包包含以下信息:

圖2 單層系統(tǒng)模型Fig 2 Single-layer system model

圖3 環(huán)形集合模型Fig 3 Ring set model

MA_ID 是MA 的身份標志;MA_Num 表示MA 當前數(shù)量，每產(chǎn)生一個新的MA，此變量加1;SourceList 為基站所需信息所在的節(jié)點列表;FloorList 是通過SourceList 得出的需要訪問的層列表;AccessedFlag 表示單層系統(tǒng)是否被訪問;FirstFloor 和LastFloor 分別代表FloorList 中第一個和最后一個需要訪問的層;Processing code 用于處理感興趣的信息;Message 是經(jīng)壓縮和數(shù)據(jù)融合的消息包。

2 基于三維胞元空間的3D—BPMA 算法

2.1 信息交換的基本路徑

3D—BPMA 算法包含節(jié)點收集的消息包和MA 數(shù)據(jù)包。前者在胞元內(nèi)由胞子傳輸?shù)桨?，后者在基站與路由器、路由器與路由器、路由器與胞父、胞父與胞父之間傳輸。兩種信息交互路徑如圖4 所示，F(xiàn)loorNum=0 的基站將MA 發(fā)送給FloorNum=1 或FloorNum=－1 的層，根據(jù)需要將MA 進行復制轉(zhuǎn)發(fā)給相應的層，等收集完MA 數(shù)據(jù)包內(nèi)SourceList所有的節(jié)點信息后，消息包經(jīng)路由器回到基站。

圖4 信息交互示意圖Fig 4 Sketch map of information interaction

2.2 MA 雙向并行傳輸策略

環(huán)形集合將單層系統(tǒng)分割為不同的區(qū)域，這為MA 并行訪問提供了可能。根據(jù)圖3 所示環(huán)形集合在XOY 平面的投影，規(guī)定MA 并行傳輸策略:RingSetK－1復制發(fā)送MA數(shù)據(jù)包到達RingSetK(K ＞0)內(nèi)靠近原點的胞父FK;然后MA 在胞父FK處同時按逆時針和順時針訪問胞元區(qū)域;最后MA 回到本層路由器。MA 的并行傳輸策略如圖5 所示，其中RingSet1接收到路由器發(fā)送的MA 數(shù)據(jù)包，同時復制并發(fā)送MA 到RingSet2，RingSet2復制并發(fā)送MA 到Ring-Set3，在RingSet3內(nèi)的F3中，根據(jù)數(shù)據(jù)包內(nèi)的SourceList，MA 在逆時針和順時針兩個方向同時訪問胞元，最后回到路由器。其中每個胞元內(nèi)有若干胞子節(jié)點，對于單個胞元來說，當胞父能量下降到βEini(0 ＜β ＜1，β 為低能量報警系數(shù))時節(jié)點內(nèi)部開始進行自適應選舉，由能量較大的節(jié)點擔當胞父，實現(xiàn)能耗平衡，保證MA 線路的穩(wěn)定性。

圖5 MA 并行傳輸策略Fig 5 Parallel transmission strategy of MA

2.3 基于三維胞元空間的3D—BPMA 算法流程

3D—BPMA 算法的實現(xiàn)分為三部分:1)基站派出MA 經(jīng)路由器到達所需的FloorNum;2)MA 在本層系統(tǒng)內(nèi)通過行訪問策略完成SourceList 內(nèi)所有節(jié)點的訪問，回到本層的路由器;3)完成收集數(shù)據(jù)的MA 經(jīng)路由器轉(zhuǎn)發(fā)回到基站。具體流程如圖6 所示，其中存在雙向并行模式:一個橫向并行方式，即MA 在單層系統(tǒng)中訪問胞元是并行的，這種方式能夠提高能量的利用率;另外一個是縱向并行方式，即MA 在路由器之間的轉(zhuǎn)發(fā)和MA 在每個單層系統(tǒng)中的并行訪問是互不干擾的，這種并行能夠防止信道阻塞，提升搜集節(jié)點信息的效率。

3 仿真實驗

3.1 仿真參數(shù)設(shè)定

算法仿真是在OMNeT++V4.1 平臺上進行的。本文分別從平均能耗、平均響應時間和MA 發(fā)送率等三個方面進行比較，參數(shù)設(shè)定為:胞元邊長d 為50 m;節(jié)點原始感應數(shù)據(jù)大小為20 bit;初始MA 大小為100 bit;節(jié)點初始能量Eini為200 J;接收或發(fā)送常數(shù)Eelec為50 nJ/bit;信號衰減常數(shù)εamp為100 pJ/bit/m2;數(shù)據(jù)融合能耗Ea為5 nJ/bit;低能量報警系數(shù)β 為0.3;數(shù)據(jù)感應能耗Es為2 nJ/bit;MA 的壓縮率r 為0.8;MA 的融合率ρ 為0.8。

3.2 仿真結(jié)果分析

三種算法的平均能耗隨著輪數(shù)變化的曲線如圖7 所示。3D—BPMA 算法通過雙向并行MA 訪問策略實現(xiàn)了MA路徑的優(yōu)化，并采用胞父先搜集并融合本胞元內(nèi)胞子節(jié)點信息的方式，減少了迂回路線，故平均能耗較低。而DSG—MIP 算法采用了簡單并行方式，相比LCF 而言，迂回路線較短，故其平均能耗較低。

圖6 3D—BPMA 算法流程Fig 6 Process of 3D—BPMA algorithm

圖7 平均能耗比較Fig 7 Comparison of average energy consumption

三種算法的平均響應時間隨著輪數(shù)變化的曲線如圖8所示。3D—BPMA 相比較LCF 和DSG—MIP 每個MA 訪問的節(jié)點數(shù)減少，并且是并行進行，所以，減少了平均響應時間。LCF 算法中MA 逐個進行節(jié)點訪問，所以，平均響應時間最長。

三種算法的MA 發(fā)送率隨著輪數(shù)變化的曲線如圖9 所示。相比LCF 和DSG—MIP，3D—BPMA 中MA 數(shù)據(jù)量不大，能保證胞父節(jié)點順利完成發(fā)送MA，而LCF 和DSG—MIP 算法因為MA 訪問較多的源節(jié)點導致MA 數(shù)據(jù)量過大，節(jié)點因轉(zhuǎn)發(fā)數(shù)據(jù)較大的MA 而死亡，降低了MA 發(fā)送率。

4 結(jié) 論

3D—BPMA 算法根據(jù)單層胞元系統(tǒng)的特性，合理地復制MA，同時進行橫向與縱向并行訪問，降低訪問源節(jié)點的平均響應時間;依靠及時選舉機制保證了MA 在轉(zhuǎn)發(fā)過程中路徑的穩(wěn)定性，提高了MA 的發(fā)送率。仿真結(jié)果驗證其高效的反應速度和較高的能量利用率，克服了單一MA 造成的問題。進一步的研究計劃是根據(jù)節(jié)點的具體地理位置優(yōu)化MA 的訪問路徑。

圖8 平均響應時間比較Fig 8 Comparison of average response time

圖9 發(fā)送率比較Fig 9 Comparison of delivery rate

［1］ Ian F Akyildiz，Tommaso Melodia，Kaushik R Chowdhury.A survey on wireless multimedia sensor networks［J］.Computer Networks，2007，51(4):921－960.

［2］ Huang Haojun，Hu Guangmin，Yu Fucai.Energy-aware geographic routing in wireless sensor networks with anchor nodes［J］.International Journal of Communication Systems，2013，26(1):100－113.

［3］ 胡曉敏.無線傳感器網(wǎng)絡(luò)Agent 數(shù)據(jù)分流策略［J］.軟件學報，2012，23(11):2946－2954.

［4］ Singh Yashpal，Deep Kamal，Niranjan S.Multiple criteria clustering of mobile agents in WSNs［J］.International Journal of Wireless＆Mobile Networks(IJWMN)，2012，4(3):183－193.

［5］ Qi H，Iyengar S S，Chakrabarty K.Multiresolution data integration using mobile agents in distributed sensor networks［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2001，31(3):383－391.

［6］ Chen M，Gonzalez-Valenzuela S，Leung V C M.Directional source grouping for multi-agent itinerary planning in wireless sensor networks［C］∥2010 International Conference on Information and Communication Technology Convergence(ICTC)，IEEE，2010:207－212.

［7］ 柯 濤，孫 暉，劉俊延，等.基于三維胞元空間的無線傳感器路由算法［J］.電子與信息學報，2013，35(6):1298－1304.

［8］ Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of the Hawaiian International Conference on System Sciences，Hawaii，2000:1－10.

［9］ Chen M，Yang L T，Kwon T，et al.Itinerary planning for energyefficient agent communications in wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2011，60(7):3290－3299.