基于三維胞元空間的MA 雙向并行路由算法

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

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

0 引 言

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

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

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

1 相關模型

1.1 三維胞元空間模型

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

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

1.2 能耗模型與數據融合模型

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

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

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

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

1.3 單層系統模型

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

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

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

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

4)環形集合(RingSet):如果將到達路由器跳數相同的胞父節點視作一個集合，單層系統模型被分割成環形集合，RingSetK(K∈N)為該層的第K 個環形集合，其中路由器所在的集合是RingSet0。如圖3，F1，F2與F3是本層內靠近原點的胞父，其分別所屬環形集合RingSet1，RingSet2，Ring-Set3。

1.4 MA 的數據包格式

本文定義MA 的數據包包含以下信息:

圖2 單層系統模型Fig 2 Single-layer system model

圖3 環形集合模型Fig 3 Ring set model

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

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

2.1 信息交換的基本路徑

3D—BPMA 算法包含節點收集的消息包和MA 數據包。前者在胞元內由胞子傳輸到胞父，后者在基站與路由器、路由器與路由器、路由器與胞父、胞父與胞父之間傳輸。兩種信息交互路徑如圖4 所示，FloorNum=0 的基站將MA 發送給FloorNum=1 或FloorNum=－1 的層，根據需要將MA 進行復制轉發給相應的層，等收集完MA 數據包內SourceList所有的節點信息后，消息包經路由器回到基站。

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

2.2 MA 雙向并行傳輸策略

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

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

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

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

3 仿真實驗

3.1 仿真參數設定

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

3.2 仿真結果分析

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

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

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

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

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

4 結 論

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

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

圖9 發送率比較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］ 胡曉敏.無線傳感器網絡Agent 數據分流策略［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.