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

黃光群，孫 暉，路 揚(yáng)，詹亞曙

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

0 引 言

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

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

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

1 相關(guān)模型

1.1 三維胞元空間模型

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

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

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

本文采用文獻(xiàn)［8］中的能耗模型，當(dāng)傳輸g bit 時(shí)

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

本文采用文獻(xiàn)［9］的數(shù)據(jù)融合模型，訪問第k 個(gè)節(jié)點(diǎn)時(shí)MA 的表達(dá)式如下

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

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

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

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

2)層數(shù)(FloorNum):基站的胞元坐標(biāo)為(XB，YB，ZB)，路由器的胞元坐標(biāo)為(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):如果將到達(dá)路由器跳數(shù)相同的胞父節(jié)點(diǎn)視作一個(gè)集合，單層系統(tǒng)模型被分割成環(huán)形集合，RingSetK(K∈N)為該層的第K 個(gè)環(huán)形集合，其中路由器所在的集合是RingSet0。如圖3，F(xiàn)1，F(xiàn)2與F3是本層內(nèi)靠近原點(diǎn)的胞父，其分別所屬環(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 的身份標(biāo)志;MA_Num 表示MA 當(dāng)前數(shù)量，每產(chǎn)生一個(gè)新的MA，此變量加1;SourceList 為基站所需信息所在的節(jié)點(diǎn)列表;FloorList 是通過(guò)SourceList 得出的需要訪問的層列表;AccessedFlag 表示單層系統(tǒng)是否被訪問;FirstFloor 和LastFloor 分別代表FloorList 中第一個(gè)和最后一個(gè)需要訪問的層;Processing code 用于處理感興趣的信息;Message 是經(jīng)壓縮和數(shù)據(jù)融合的消息包。

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

2.1 信息交換的基本路徑

3D—BPMA 算法包含節(jié)點(diǎn)收集的消息包和MA 數(shù)據(jù)包。前者在胞元內(nèi)由胞子傳輸?shù)桨?，后者在基站與路由器、路由器與路由器、路由器與胞父、胞父與胞父之間傳輸。兩種信息交互路徑如圖4 所示，F(xiàn)loorNum=0 的基站將MA 發(fā)送給FloorNum=1 或FloorNum=－1 的層，根據(jù)需要將MA 進(jìn)行復(fù)制轉(zhuǎn)發(fā)給相應(yīng)的層，等收集完MA 數(shù)據(jù)包內(nèi)SourceList所有的節(jié)點(diǎn)信息后，消息包經(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ù)制發(fā)送MA數(shù)據(jù)包到達(dá)RingSetK(K ＞0)內(nèi)靠近原點(diǎn)的胞父FK;然后MA 在胞父FK處同時(shí)按逆時(shí)針和順時(shí)針訪問胞元區(qū)域;最后MA 回到本層路由器。MA 的并行傳輸策略如圖5 所示，其中RingSet1接收到路由器發(fā)送的MA 數(shù)據(jù)包，同時(shí)復(fù)制并發(fā)送MA 到RingSet2，RingSet2復(fù)制并發(fā)送MA 到Ring-Set3，在RingSet3內(nèi)的F3中，根據(jù)數(shù)據(jù)包內(nèi)的SourceList，MA 在逆時(shí)針和順時(shí)針兩個(gè)方向同時(shí)訪問胞元，最后回到路由器。其中每個(gè)胞元內(nèi)有若干胞子節(jié)點(diǎn)，對(duì)于單個(gè)胞元來(lái)說(shuō)，當(dāng)胞父能量下降到βEini(0 ＜β ＜1，β 為低能量報(bào)警系數(shù))時(shí)節(jié)點(diǎn)內(nèi)部開始進(jìn)行自適應(yīng)選舉，由能量較大的節(jié)點(diǎn)擔(dān)當(dāng)胞父，實(shí)現(xiàn)能耗平衡，保證MA 線路的穩(wěn)定性。

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

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

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

3 仿真實(shí)驗(yàn)

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

4 結(jié) 論

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

圖8 平均響應(yīng)時(shí)間比較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ú)線傳感器網(wǎng)絡(luò)Agent 數(shù)據(jù)分流策略［J］.軟件學(xué)報(bào)，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］ 柯 濤，孫 暉，劉俊延，等.基于三維胞元空間的無(wú)線傳感器路由算法［J］.電子與信息學(xué)報(bào)，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.