任 智，張 勇，彭 晨，武 楊

（重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

基于位置感知的高效發(fā)布/訂閱路由算法

任 智，張 勇，彭 晨，武 楊

（重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

針對(duì)現(xiàn)有結(jié)合地理位置信息的移動(dòng)Ad hoc（自組織）網(wǎng)絡(luò)路由算法中節(jié)點(diǎn)在更新位置信息和回應(yīng)請(qǐng)求時(shí)增加控制包開(kāi)銷的問(wèn)題，提出了一種EPRLM（基于位置感知的移動(dòng)Ad hoc網(wǎng)絡(luò)高效發(fā)布/訂閱路由算法）。EPRLM結(jié)合基于NFZ（節(jié)點(diǎn)轉(zhuǎn)發(fā)區(qū)域）的信息更新機(jī)制和Join Reply（加入回應(yīng)）包的捎帶機(jī)制，在節(jié)點(diǎn)發(fā)布內(nèi)容的過(guò)程中，分析位置信息并及時(shí)更新，同時(shí)適當(dāng)減少控制包的轉(zhuǎn)發(fā)。

移動(dòng)自組織網(wǎng)絡(luò)；發(fā)布/訂閱；內(nèi)容路由；位置感知

0 引 言

發(fā)布/訂閱系統(tǒng)［1］在信息生成和接受兩者間具有弱耦合、非同步及多點(diǎn)通信的特點(diǎn)，成為很多網(wǎng)絡(luò)應(yīng)用的一種重要組件［2］，尤其適用于具有動(dòng)態(tài)拓?fù)涮匦缘囊苿?dòng)Ad hoc（自組織）網(wǎng)絡(luò)。

針對(duì)移動(dòng)Ad hoc網(wǎng)絡(luò)中基于位置的發(fā)布/訂閱路由算法，目前已有一些研究。文獻(xiàn)［3］提出了一種STEAM（基于附近和分布式過(guò)濾的區(qū)域事件轉(zhuǎn)發(fā)群組算法），在該算法中，訂閱節(jié)點(diǎn)只訂閱附近發(fā)布方的內(nèi)容。這導(dǎo)致只能在發(fā)布內(nèi)容時(shí)分發(fā)內(nèi)容給目標(biāo)區(qū)域內(nèi)的節(jié)點(diǎn)，限制了內(nèi)容的發(fā)布與匹配。文獻(xiàn)［4］提出了INGEO（基于內(nèi)部地理位置的路由協(xié)議）算法，該算法以速度位移矢量來(lái)重新定位移動(dòng)的訂閱節(jié)點(diǎn)。文獻(xiàn)［5］提出了基于位置的自適應(yīng)路由算法，在合理的區(qū)域內(nèi)實(shí)現(xiàn)內(nèi)容的分發(fā)和匹配。但該算法較少考慮節(jié)點(diǎn)的移動(dòng)性，以節(jié)點(diǎn)的請(qǐng)求頻次計(jì)算的結(jié)果因節(jié)點(diǎn)頻繁移動(dòng)而不準(zhǔn)確，并且所有節(jié)點(diǎn)的區(qū)域頻繁更新所帶來(lái)的開(kāi)銷很大。文獻(xiàn)［6］提出的Courier算法（基于位置感知的有效群組通信算法），類似源路由算法LGS（以位置為導(dǎo)向的小區(qū)多播生成樹(shù)算法）［7］，訂閱節(jié)點(diǎn)將速度位置信息嵌在Hello包內(nèi)，再轉(zhuǎn)發(fā)至內(nèi)容發(fā)布方，依靠訂閱節(jié)點(diǎn)及時(shí)更新信息，發(fā)布方計(jì)算發(fā)布內(nèi)容所需轉(zhuǎn)發(fā)的路徑轉(zhuǎn)發(fā)樹(shù)和受限泛洪區(qū)域的大小，實(shí)現(xiàn)目標(biāo)區(qū)域節(jié)點(diǎn)的內(nèi)容匹配。基于上述分析，以Courier算法為代表的基于位置感知的路由算法對(duì)于位置速度信息的更新要求頻繁，且Hello包存在冗余廣播問(wèn)題。本文在文獻(xiàn)［6］的基礎(chǔ)上提出一種EPRLM（基于位置感知的移動(dòng)Ad hoc網(wǎng)絡(luò)高效發(fā)布/訂閱路由算法）。本文的主要貢獻(xiàn)有:（1）在內(nèi)容消息接收過(guò)程中，節(jié)點(diǎn)通過(guò)計(jì)算自身是否移出區(qū)域來(lái)判斷是否更新位置速度信息，從而減少了不必要的控制數(shù)據(jù)包轉(zhuǎn)發(fā)；（2）訂閱節(jié)點(diǎn)的回應(yīng)包可以捎帶之后的Hello包信息，減少了冗余Hello包的廣播。

1 網(wǎng)絡(luò)模型與問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

定義1（節(jié)點(diǎn)轉(zhuǎn)發(fā)區(qū)域）如圖1所示。在t1時(shí)刻，源節(jié)點(diǎn)srcA收到訂閱節(jié)點(diǎn)memB的位置更新信息；在t2時(shí)刻（t2＞t1），srcA發(fā)送數(shù)據(jù)給memB；memB在t1～t2這個(gè)時(shí)間段內(nèi)能夠移動(dòng)的范圍是以srcA存儲(chǔ)的memB位置為中心、半徑為VB（t2-t1）的圓形區(qū)域，即NFZ（節(jié)點(diǎn)轉(zhuǎn)發(fā)區(qū)域）。

圖1 節(jié)點(diǎn)轉(zhuǎn)發(fā)區(qū)域

定義2（群組轉(zhuǎn)發(fā)區(qū)域）如圖2所示。srcA發(fā)布內(nèi)容給多個(gè)訂閱節(jié)點(diǎn)時(shí)，需要優(yōu)化轉(zhuǎn)發(fā)區(qū)域。首先srcA降序排列訂閱節(jié)點(diǎn)的NFZ大小，然后判斷NFZC和NFZB的關(guān)系。如果二者相交，并且半角α1小于閾值［6］，則合并兩區(qū)域；如果兩區(qū)域中的一個(gè)區(qū)域包含另一區(qū)域，則將其合并為一個(gè)區(qū)域；如果兩區(qū)域并不包含或者相交，但是半角α1小于閾值［6］，則合并兩區(qū)域。至此，形成GFZ（群組轉(zhuǎn)發(fā)區(qū)域）。

圖2 群組轉(zhuǎn)發(fā)區(qū)域

定義3（歐幾里德Steiner樹(shù)）如圖3所示。A、B和C為網(wǎng)絡(luò)中的3個(gè)節(jié)點(diǎn)，S為歐幾里德Steiner節(jié)點(diǎn)（即網(wǎng)絡(luò)中的虛擬中繼節(jié)點(diǎn)）。節(jié)點(diǎn)A發(fā)送給B和C的總的開(kāi)銷，可以經(jīng)過(guò)S（實(shí)際中也可以是S的附近節(jié)點(diǎn)）再分別分發(fā)至B和C。而對(duì)于多個(gè)訂閱節(jié)點(diǎn)的GFZ，此時(shí)可以通過(guò)迭代計(jì)算出適合的歐幾里德Steiner樹(shù)。

圖3 歐幾里德Steiner樹(shù)區(qū)域

1.2 問(wèn)題描述

以Courier算法為代表的基于位置感知的路由算法存在以下問(wèn)題:

（1）位置速度信息需要通過(guò)Hello消息頻繁更新。而在節(jié)點(diǎn)沒(méi)有離開(kāi)NFZ時(shí)，上次更新的信息依然可以將內(nèi)容轉(zhuǎn)發(fā)至此區(qū)域，并實(shí)現(xiàn)區(qū)域泛洪，使得節(jié)點(diǎn)收到此發(fā)布內(nèi)容。此時(shí)，更新導(dǎo)致冗余開(kāi)銷。

（2）在訂閱節(jié)點(diǎn)回應(yīng)源節(jié)點(diǎn)的請(qǐng)求包（Join Request）時(shí)，回應(yīng)包（Join Reply）和之后一次的Hello包所起作用重復(fù)，產(chǎn)生冗余。

2 EPRLM

EPRLM采用基于NFZ的信息更新以及Join Reply包的捎帶等新機(jī)制，從而達(dá)到內(nèi)容消息與訂閱節(jié)點(diǎn)的高效匹配，降低控制開(kāi)銷的效果。

2.1 EPRLM新機(jī)制

2.1.1基于NFZ的信息更新機(jī)制

Courier算法只考慮了訂閱節(jié)點(diǎn)位置速度信息改變后，通過(guò)Hello消息通知發(fā)布節(jié)點(diǎn)。但是，如果訂閱節(jié)點(diǎn)在接收內(nèi)容消息時(shí)并沒(méi)有移出NFZ，此時(shí)內(nèi)容消息已經(jīng)在轉(zhuǎn)發(fā)的路徑上，那么此次位置速度信息的更新就不會(huì)起作用，發(fā)布節(jié)點(diǎn)基于上次的位置速度信息依然可以將消息泛洪至訂閱節(jié)點(diǎn)。因此，訂閱節(jié)點(diǎn)在接收內(nèi)容消息時(shí)，位置速度信息如果發(fā)生變更，首先判斷訂閱節(jié)點(diǎn)自身是否移出上次位置速度信息更新到目前為止的NFZ。如果已經(jīng)移出，則通過(guò)Hello包更新位置速度信息，否則，在位置速度信息失效前不再更新。

這種嘗試對(duì)職業(yè)院校無(wú)疑是有幫助的，但對(duì)企業(yè)來(lái)說(shuō)也存在一些抱怨，如教師對(duì)產(chǎn)品開(kāi)發(fā)缺乏經(jīng)驗(yàn)導(dǎo)致校企磨合周期很長(zhǎng)，效率過(guò)低導(dǎo)致公司技術(shù)人員對(duì)此持消極態(tài)度，教師對(duì)產(chǎn)品開(kāi)發(fā)過(guò)程不熟導(dǎo)致浪費(fèi)的材料很多，教師對(duì)課程資源開(kāi)發(fā)不熟導(dǎo)致占用企業(yè)技術(shù)人員太多時(shí)間，影響公司正常運(yùn)作。

通過(guò)基于NFZ的信息更新，可以減少頻繁轉(zhuǎn)發(fā)至發(fā)布節(jié)點(diǎn)的信息更新Hello包，從而減少網(wǎng)絡(luò)的控制開(kāi)銷，減緩網(wǎng)絡(luò)的通信負(fù)荷。

2.1.2 Join Reply包的捎帶機(jī)制

在Courier原算法中，訂閱節(jié)點(diǎn)收到發(fā)布節(jié)點(diǎn)的請(qǐng)求包Join Request時(shí)，需要回應(yīng)Join Reply包；并且在回應(yīng)包到達(dá)發(fā)布節(jié)點(diǎn)的過(guò)程中，對(duì)應(yīng)路徑上的節(jié)點(diǎn)須轉(zhuǎn)發(fā)此消息。此后，產(chǎn)生或轉(zhuǎn)發(fā)回應(yīng)包的節(jié)點(diǎn)需要廣播Hello包告知鄰居節(jié)點(diǎn)自己的狀態(tài)信息，而該Hello包的信息與先前回應(yīng)包的信息重合，產(chǎn)生冗余。本算法提出了Join Reply包的捎帶機(jī)制，改變Join Reply包的消息類型并在轉(zhuǎn)發(fā)時(shí)廣播此消息，此時(shí)除轉(zhuǎn)發(fā)至發(fā)布節(jié)點(diǎn)路徑上的節(jié)點(diǎn)需要繼續(xù)廣播此包外，其余節(jié)點(diǎn)收到Join Reply包后將其當(dāng)作Hello包提取信息。

Join Reply包的捎帶機(jī)制將訂閱節(jié)點(diǎn)至發(fā)布節(jié)點(diǎn)路徑上所有節(jié)點(diǎn)的一次Hello包廣播的信息由Join Reply包捎帶完成，降低了冗余控制開(kāi)銷，減少了信道資源的競(jìng)爭(zhēng)。

2.2 算法操作

EPRLM的主要操作步驟如下:

（1）發(fā)布節(jié)點(diǎn)周期性全網(wǎng)泛洪Join Request包（包含發(fā)布節(jié)點(diǎn)ID、位置及內(nèi)容摘要等信息）。

（2）節(jié)點(diǎn)收到Join Request包后，如需要發(fā)布節(jié)點(diǎn)所擁有的內(nèi)容，則回復(fù)Join Reply包（包含該節(jié)點(diǎn)ID、位置和速度等信息）并在轉(zhuǎn)發(fā)時(shí)廣播此消息，此時(shí)除轉(zhuǎn)發(fā)至發(fā)布節(jié)點(diǎn)路徑上的節(jié)點(diǎn)需要繼續(xù)廣播此包外，其余節(jié)點(diǎn)收到Join Reply包后將其當(dāng)作Hello包提取信息。

（3）節(jié)點(diǎn)收到Join Request包后，如不需要發(fā)布節(jié)點(diǎn)所擁有的內(nèi)容，則繼續(xù)廣播此消息。

（5）訂閱節(jié)點(diǎn)的位置速度發(fā)生變化需要更新時(shí)，首先判斷訂閱節(jié)點(diǎn)自身是否移出上次位置速度信息更新到目前為止的NFZ。如果已經(jīng)移出，則通過(guò)Hello包更新位置速度信息；否則，在位置速度信息失效前不再更新。

3 仿真

本文使用OPNET［8］作為仿真軟件平臺(tái)，選取LGS算法和Courier算法作為與EPRLM進(jìn)行比較的對(duì)象，在相同仿真條件下（仿真參數(shù)設(shè)置如表1所示）分析比較3種算法的消息傳送成功率、消息端到端時(shí)延、內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)和控制包開(kāi)銷等性能。其中，實(shí)際的消息端到端時(shí)延等于平均跳數(shù)乘以每一跳的平均轉(zhuǎn)發(fā)時(shí)間，而每一跳的平均轉(zhuǎn)發(fā)時(shí)間依賴于具體的硬件條件；內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)為內(nèi)容消息成功到達(dá)所有訂閱節(jié)點(diǎn)所需轉(zhuǎn)發(fā)的總次數(shù)。

表1 仿真默認(rèn)參數(shù)

（1）消息傳送成功率

3種算法的消息傳送成功率仿真結(jié)果如表2所示。從表中可以看出，EPRLM的消息傳送成功率高于Courier和LGS算法，這是因?yàn)榛贜FZ的信息更新機(jī)制減少了Hello包的產(chǎn)生和轉(zhuǎn)發(fā)，而且此時(shí)減少的Hello包原本是沿著與內(nèi)容消息傳播的反方向路徑轉(zhuǎn)發(fā)的，由此減少了沖突和資源競(jìng)爭(zhēng)。同樣，Join Reply包的捎帶機(jī)制也降低了信道中資源的競(jìng)爭(zhēng)。

表2 3種算法的消息傳送成功率對(duì)比

（2）消息端到端時(shí)延

3種算法的消息端到端時(shí)延仿真結(jié)果如圖4所示。由圖可見(jiàn)，EPRLM的消息端到端時(shí)延低于Courier和LGS算法，這是因?yàn)镋PRLM中基于NFZ的位置信息更新機(jī)制減少了Hello包的數(shù)量，降低了與反方向路徑內(nèi)容消息的轉(zhuǎn)發(fā)而產(chǎn)生的信道和資源競(jìng)爭(zhēng)，減少了同一路徑上轉(zhuǎn)發(fā)消息的負(fù)擔(dān)；另外，Join Reply包的捎帶機(jī)制同樣降低了信道中資源的競(jìng)爭(zhēng)。平均跳數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目增加而減少的原因是:在密集網(wǎng)絡(luò)中發(fā)現(xiàn)源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間最短路徑的概率會(huì)更高一些。

圖4 3種算法的消息端到端時(shí)延比較

（3）內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)

在不同節(jié)點(diǎn)數(shù)時(shí)3種算法的內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)比較如圖5所示。從圖中可以看出，隨著節(jié)點(diǎn)數(shù)的增多，3種算法的內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)都是遞增的。EPRLM的內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)比其他兩種算法低，主要是因?yàn)镋PRLM的兩種新機(jī)制減少了Hello包的產(chǎn)生和轉(zhuǎn)發(fā)，減少了信道資源的競(jìng)爭(zhēng)和沖突，因而減少了內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)。

圖5 3種算法的內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)比較

（4）控制包開(kāi)銷

圖6給出了不同節(jié)點(diǎn)數(shù)下3種算法的控制包開(kāi)銷的比較。由圖可見(jiàn)，相對(duì)于Courier和LGS算法，EPRLM在不同節(jié)點(diǎn)數(shù)下的控制包開(kāi)銷都是最少的，這是因?yàn)榛贜FZ的位置信息更新機(jī)制和Join Reply包的捎帶機(jī)制都減少了Hello包的產(chǎn)生和轉(zhuǎn)發(fā)，且減少的沖突和資源競(jìng)爭(zhēng)帶來(lái)的控制包開(kāi)銷的降低也很可觀。

圖6 3種算法的控制包開(kāi)銷比較

4 結(jié)束語(yǔ)

針對(duì)結(jié)合地理位置信息的發(fā)布/訂閱內(nèi)容路由算法中節(jié)點(diǎn)頻繁更新位置信息和控制包存在冗余的問(wèn)題，本文提出了EPRLM。仿真驗(yàn)證表明，與Courier和LGS算法相比，EPRLM能夠很好地提高網(wǎng)絡(luò)中節(jié)點(diǎn)的消息傳送成功率，并降低網(wǎng)絡(luò)吞吐量，減少消息時(shí)延和發(fā)送次數(shù)，降低控制開(kāi)銷。

［1］Carzaniga A，Rosenblum D S，Wolf A L.Design and evaluation of a widearea event notification service［J］.ACM Transactions on Computer Systems，2001，19（3）:332-383.

［2］Rezende G C，Rocha B，Loureiro A.Publish/subscribe architecture for mobile ad hoc networks［C］// Proc of the ACM Symposium on Applied Computing 2008.Fortaleza，Brazil:ACM，2008:1913-1917.

［3］Rene M，Vinny C.On event-based middleware for location-aware mobile applications［C］//IEEE Transactions on Software Engineering 2010.Los Alamitos: IEEE，2010，36（3）:409-430.

［4］Hai L，Houda L.INGEO:indoor geographic routing protocol for MANETs［C］//In Proceedings of the 3rd International Conference on Mobile Computing and U-biquitous Networking 2006.San Jose:ACM，2006: 224-229.

［5］Holzer A，Eugster P，Garbinato B.ALPS-Adaptive Location-based Publish/Subscribe［J］.Computer Networks，2012，56（12）:2949-2962.

［6］Mitra P，Poellabauer C.Efficient group communications in location aware mobile ad-hoc networks［J］.Pervasive and Mobile Computing，2012，（8）:229-248.

［7］Chen K，Nahrstedt K.Effective location-guided tree construction algorithms for small group multicast in MANET［C］//In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies 2002.New York:IEEE，2002:1180-1189.

［8］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.北京:清華大學(xué)出版社，2004.

Efficient Publish/Subscribe Routing Based on Location Aware

REN Zhi，ZHANG Yong，PENG Chen，WU Yang
（Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

To solve the problem that the nodes updating the location information and respond to requests which increases the control packet overhead in existing content routing based on location aware for mobile Ad hoc networks，an Efficient Publish/ subscribe Routing based on Location aware for Mobile Ad hoc networks（EPRLM）is proposed.Combining information update based on NFZ area mechanism and piggybacking mechanism of join reply packet，EPRLM analyzes the location information and update on time to reduce the control packet forwarding appropriately in the process of publishing content.

mobile Ad hoc networks；publish/subscribe；content routing；location aware

TP393

A

1005-8788（2016）05-0075-04

10.13756/j.gtxyj.2016.05.022

2016-03-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（61379159）；長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃基金資助項(xiàng)目（IRT1299）

任智（1971-），男，四川內(nèi)江人。教授，博士，主要研究方向?yàn)閷拵o(wú)線移動(dòng)通信網(wǎng)絡(luò)原理與技術(shù)。