蘇 暢，臧李立，尙鳳軍，趙 曜

(1.重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065;2.美國康奈爾大學(xué)計(jì)算機(jī)系，紐約州伊薩卡市，美國)

隨著無線傳感器網(wǎng)絡(luò)［1］技術(shù)的進(jìn)一步發(fā)展，其應(yīng)用領(lǐng)域越來越廣。傳感器節(jié)點(diǎn)的能量受限以及對(duì)數(shù)據(jù)實(shí)時(shí)性的高要求使得低能耗和低延遲成為無線傳感器網(wǎng)絡(luò)通信協(xié)議的重要衡量指標(biāo)?；诘乩砦恢玫穆酚蓞f(xié)議因其對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的極低需求使其算法簡(jiǎn)單高效而且開銷小，其路由發(fā)現(xiàn)和數(shù)據(jù)傳輸過程依靠節(jié)點(diǎn)自身及其鄰節(jié)點(diǎn)的位置信息(通過 GPS 等定位設(shè)備［2－6］獲取)。

無線傳感器網(wǎng)絡(luò)極強(qiáng)的應(yīng)用相關(guān)性使基于地理位置路由的地域群播(Geocasting:即源節(jié)點(diǎn)向WSN中特定地理位置區(qū)域內(nèi)的所有節(jié)點(diǎn)發(fā)送信息)應(yīng)運(yùn)而生。其應(yīng)用廣泛，如:森林管理中心需要向森林中高火險(xiǎn)區(qū)域內(nèi)所有節(jié)點(diǎn)發(fā)送命令，使區(qū)域內(nèi)節(jié)點(diǎn)及時(shí)監(jiān)測(cè)并匯報(bào)其周圍溫度狀況;交通控制中指揮中心要向交通擁擠地區(qū)所有節(jié)點(diǎn)及時(shí)發(fā)出控制命令。

地域群播通過兩個(gè)過程完成傳輸:源節(jié)點(diǎn)與目標(biāo)區(qū)域的通信及目標(biāo)區(qū)域內(nèi)信息的傳輸。網(wǎng)絡(luò)拓?fù)涞牟灰?guī)則性，尤其是路由空洞的存在，使信息如何低能耗、高可靠性、低延遲地傳輸?shù)侥繕?biāo)區(qū)域成為目前研究的熱點(diǎn)。Brad Karp等提出的GPSR算法［7］，以貪心算法為基礎(chǔ)，結(jié)合面路由的方法，成功解決了貪心算法因遇到路由空洞而導(dǎo)致算法失敗的問題;胥楚貴等提出的最佳匹配節(jié)點(diǎn)策略［8］通過選取距離由空洞邊界所圍成多邊形的最小覆蓋圓圓心最近的非活躍節(jié)點(diǎn)來替換失敗節(jié)點(diǎn)的方式修復(fù)覆蓋空洞;F.Yu 提出的彈性路由(Elastic Routing)算法［9］通過路由路徑的反方向更新Sink節(jié)點(diǎn)的位置信息，大大降低了能量開銷和傳輸延遲;針對(duì)密集型網(wǎng)絡(luò)的目標(biāo)區(qū)域內(nèi)信息的傳輸多采用簡(jiǎn)單泛洪的方式，如ALURP［10］、LBM［11］等算法。而實(shí)際中網(wǎng)絡(luò)的密度狀況是不可知的，稀疏網(wǎng)絡(luò)嚴(yán)重降低了網(wǎng)絡(luò)的連通度［12］，簡(jiǎn)單泛洪無法保證區(qū)域內(nèi)所有節(jié)點(diǎn)收到信息，因此 Karim Seada等提出了 GFPG［13］算法。

多目標(biāo)區(qū)域地域群播的目標(biāo)區(qū)域數(shù)量以及位置均未知，這種復(fù)雜性注定了單目標(biāo)區(qū)域算法無法滿足其需求。多路徑單地域群播算法［14］中源節(jié)點(diǎn)依次將信息傳輸?shù)矫總€(gè)目標(biāo)區(qū)域內(nèi)，能量開銷極大;簡(jiǎn)單目標(biāo)區(qū)域鏈算法［14］通過鏈接所有目標(biāo)區(qū)域減少了源節(jié)點(diǎn)的能量開銷，但整個(gè)網(wǎng)絡(luò)的能量開銷依然很大;Lee Sung-Hee等提出的單費(fèi)馬點(diǎn)鏈算法［12］將所有目標(biāo)區(qū)域與源節(jié)點(diǎn)連接到一條費(fèi)馬點(diǎn)鏈上，如圖1(a)所示，雖然可以降低整個(gè)網(wǎng)絡(luò)的能量消耗，但是其健壯性和網(wǎng)絡(luò)傳輸延遲存在著缺陷。

圖1 多地域群播算法

本文提出一種基于多費(fèi)馬點(diǎn)鏈低能耗低延遲多地域群播算法，在保持較低能量消耗的基礎(chǔ)上，降低了傳輸延遲，并在NS2環(huán)境下對(duì)LLA算法和現(xiàn)有的算法進(jìn)行仿真分析。

1 多費(fèi)馬點(diǎn)鏈算法

多費(fèi)馬點(diǎn)鏈算法包括兩部分:第1是基于源節(jié)點(diǎn)傳輸區(qū)域的網(wǎng)格劃分以及網(wǎng)格中簇頭的選擇，第2是通過引入四邊形費(fèi)馬點(diǎn)解決建立三角形費(fèi)馬點(diǎn)失敗的問題，如圖1(b)所示。

1.1 網(wǎng)格劃分及簇頭選擇

假設(shè)數(shù)據(jù)源節(jié)點(diǎn)A的位置坐標(biāo)為(x0，y0)，則以該節(jié)點(diǎn)為中心建立如下坐標(biāo)系:以直線y=y0為該坐標(biāo)系的x軸，以直線x=x0為該坐標(biāo)系的y軸。此坐標(biāo)系將網(wǎng)絡(luò)分成四網(wǎng)格。當(dāng)多數(shù)目標(biāo)區(qū)域集中于某一網(wǎng)格中時(shí)，按如下規(guī)則劃分:假設(shè)網(wǎng)絡(luò)中目標(biāo)區(qū)域數(shù)量為n，網(wǎng)格劃分的層次為N

直到經(jīng)過N次劃分的網(wǎng)格中的目標(biāo)區(qū)域的數(shù)量小于等于n/2N或網(wǎng)格中的目標(biāo)區(qū)域數(shù)量均≤4。

網(wǎng)格中選取距離源節(jié)點(diǎn)最近的目標(biāo)區(qū)域的中心點(diǎn)作為該網(wǎng)格的簇頭，不同源節(jié)點(diǎn)對(duì)于不同的目標(biāo)區(qū)域產(chǎn)生不同的簇頭節(jié)點(diǎn)，避免了固定或單一簇頭導(dǎo)致其消耗能量過快而死亡。

下面對(duì)基于源節(jié)點(diǎn)傳輸區(qū)域的網(wǎng)格劃分及網(wǎng)格中選取距離源節(jié)點(diǎn)最近的目標(biāo)區(qū)域作為簇頭的方法進(jìn)行性能分析。

假設(shè)有n個(gè)目標(biāo)區(qū)域，費(fèi)馬點(diǎn)之間的平均傳輸延遲為t，費(fèi)馬點(diǎn)到其相鄰節(jié)點(diǎn)之間的傳輸延遲平均為 T，則:

?delay(n)=nt+T，(delay(n)為第n個(gè)節(jié)點(diǎn)接收到數(shù)據(jù)包時(shí)的延遲時(shí)間)(avg(delay(n))為n個(gè)目標(biāo)區(qū)域接收到數(shù)據(jù)包時(shí)的平均延遲時(shí)間)。分成網(wǎng)格后，每個(gè)網(wǎng)格有n/4個(gè)目標(biāo)區(qū)域，由于數(shù)據(jù)在網(wǎng)格內(nèi)同時(shí)通信，其平均延遲可以認(rèn)為等同于單一網(wǎng)格的延遲，考慮上面的假設(shè)，則:

通過以上分析在傳輸延遲方面該方法優(yōu)于單費(fèi)馬點(diǎn)鏈算法。源節(jié)點(diǎn)將信息傳送到簇頭節(jié)點(diǎn)后，由簇頭節(jié)點(diǎn)通過費(fèi)馬點(diǎn)鏈轉(zhuǎn)發(fā)到相應(yīng)的目標(biāo)區(qū)域內(nèi)。

1.2 網(wǎng)格費(fèi)馬點(diǎn)鏈

網(wǎng)絡(luò)中目標(biāo)區(qū)域需要向其感興趣的節(jié)點(diǎn)發(fā)送位置信息及數(shù)據(jù)收集請(qǐng)求，源節(jié)點(diǎn)則需要記錄向其發(fā)送請(qǐng)求的所有目標(biāo)區(qū)域的位置信息以便計(jì)算費(fèi)馬點(diǎn)鏈。

三角形中一定存在費(fèi)馬點(diǎn)，如圖2所示，尋找△ABC費(fèi)馬點(diǎn)的過程如下。

圖2 三角形費(fèi)馬點(diǎn)

在△APC中，將∠PAC按逆時(shí)針方向旋轉(zhuǎn)60°，點(diǎn)P和點(diǎn)C分別落于點(diǎn)P1和C'，的最小值即的最小值，即C'到點(diǎn)B的直線距離

這時(shí)點(diǎn)P和P1都在線段C'B上，同理我們可得點(diǎn)P必在線段B'A和線段A'C上，三條線段的交點(diǎn)即是三角形的費(fèi)馬點(diǎn)。因此只需找到A'、B'和C'中的任意兩點(diǎn)就可以找到該三角形的費(fèi)馬點(diǎn)，如圖2所示。

單費(fèi)馬點(diǎn)鏈算法存在著明顯的缺陷:局部能量開銷大、極大的傳輸延遲、可靠性差。當(dāng)費(fèi)馬點(diǎn)存在于三角形外部時(shí)(即三角形任意一內(nèi)角大于等于120°)，按照順序往下繼續(xù)尋找目標(biāo)區(qū)域，然后以這三個(gè)目標(biāo)區(qū)域和簇頭組成的四邊形為基礎(chǔ)，尋找四邊形的費(fèi)馬點(diǎn)，找到該費(fèi)馬點(diǎn)后，繼續(xù)尋找接下來的三角形的費(fèi)馬點(diǎn)，直到所有的目標(biāo)區(qū)域都連接到費(fèi)馬點(diǎn)鏈上。如圖3所示，有兩種情況:凸四邊形(如圖3(a)所示)和凹四邊形(如圖3(b)所示)。兩種情況下∠ABC＞120°，因此選取第四個(gè)目標(biāo)區(qū)域D形成四邊形，計(jì)算出四邊形的費(fèi)馬點(diǎn)后再以該費(fèi)馬點(diǎn)、簇頭A和下一個(gè)目標(biāo)區(qū)域的中心點(diǎn)E形成的三角形繼續(xù)尋找費(fèi)馬點(diǎn)。

圖3 四邊形費(fèi)馬點(diǎn)鏈

定理1 凸四邊形費(fèi)馬點(diǎn)的位置為對(duì)角線的交點(diǎn)。

證明:假設(shè)凸?ABCD中，對(duì)角線AC、BD交于點(diǎn)P，如圖4所示。

圖4 四邊形費(fèi)馬點(diǎn)

定理2 內(nèi)含三角形中內(nèi)三角形的兩邊之和小于外三角形的兩邊之和。

定理3 凹四邊形的費(fèi)馬點(diǎn)在凹點(diǎn)上，即四邊形內(nèi)角大于180°的頂點(diǎn)上。

證明:如圖5(b)和5(c)兩種情況所示:F點(diǎn)均為四邊形內(nèi)部異于凹點(diǎn)的任意一點(diǎn)，在圖5(b)中，△CDB是△CFB的內(nèi)含三角形，由定理2可知:

在圖5(c)中，△ADB是△AFB的內(nèi)含三角形，

由上證明可得出結(jié)論:凹四邊形的費(fèi)馬點(diǎn)在其凹點(diǎn)上。

圖5 四邊形費(fèi)馬點(diǎn)

通過引入四邊形費(fèi)馬點(diǎn)保證了所建費(fèi)馬點(diǎn)鏈的連續(xù)性，然后源節(jié)點(diǎn)將信息沿著費(fèi)馬點(diǎn)鏈傳送到所有的目標(biāo)區(qū)域，到達(dá)目標(biāo)區(qū)域的信息在該區(qū)域內(nèi)泛洪，完成地域群播路由過程。該方法能夠減少單個(gè)網(wǎng)格內(nèi)節(jié)點(diǎn)的能量消耗，降低整個(gè)網(wǎng)絡(luò)的能量開銷。

2 仿真結(jié)果與分析

2.1 仿真環(huán)境

我們使用的仿真工具是NS2.30，MAC層采用的是802.11協(xié)議。我們構(gòu)建了如下的無線傳感器網(wǎng)絡(luò):400個(gè)無線傳感器節(jié)點(diǎn)隨機(jī)地分布在2 000 m×2 000 m的正方形區(qū)域內(nèi)，地域群播區(qū)域?yàn)榘霃?50 m的圓形區(qū)域。整個(gè)仿真過程中，對(duì)每種算法我們分別設(shè)定并隨機(jī)選取網(wǎng)絡(luò)中的地域群播區(qū)域的數(shù)量為2、4、6、8、10、12、14、16 個(gè)。

仿真中我們采用三個(gè)指標(biāo)來衡量該算法的性能:包的成功傳輸比率、端到端的平均延遲和數(shù)據(jù)傳輸?shù)侥繕?biāo)區(qū)域內(nèi)這一過程中的平均能量消耗(下文簡(jiǎn)稱為平均傳輸能量消耗)。包的成功傳輸比率定義為網(wǎng)絡(luò)中所有的目標(biāo)節(jié)點(diǎn)成功接受到數(shù)據(jù)包的總量與網(wǎng)絡(luò)中所有數(shù)據(jù)源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包的總量的比值;端到端的平均延遲定義為網(wǎng)絡(luò)中所有數(shù)據(jù)包的延遲的總和與網(wǎng)絡(luò)中所有數(shù)據(jù)包總量的比值;平均傳輸能量消耗定義為網(wǎng)絡(luò)中所有傳輸?shù)臄?shù)據(jù)包的總字節(jié)數(shù)與網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包的總量和數(shù)據(jù)包成功傳輸比率的乘積的比值。

2.2 仿真結(jié)果和分析

圖6展示了數(shù)據(jù)包的成功傳輸比率。從圖中可以看出單費(fèi)馬點(diǎn)鏈算法、多路徑單地域群播算法和本文中提出的多費(fèi)馬點(diǎn)鏈算法的數(shù)據(jù)包的成功傳輸比率在95.5% ～97%之間波動(dòng)，多路徑單地域群播算法采用的是每次只向一個(gè)區(qū)域發(fā)送數(shù)據(jù)，而基于費(fèi)馬點(diǎn)鏈的兩種算法的第1階段都是采用GPSR算法，可以很好的解決導(dǎo)致成功傳輸比率下降的主要因素——路由空洞，并且對(duì)鏈路進(jìn)行了優(yōu)化。當(dāng)目標(biāo)區(qū)域數(shù)量大于6個(gè)的時(shí)候，簡(jiǎn)單目標(biāo)區(qū)域鏈算法的成功傳輸比率呈現(xiàn)線性下降趨勢(shì)，當(dāng)區(qū)域數(shù)量為12時(shí)，成功傳輸比率已降到95%，數(shù)量為16時(shí)降到93.5%，因?yàn)楹?jiǎn)單目標(biāo)區(qū)域鏈算法存在兩個(gè)方面的缺陷:無法解決路由空洞并且路由路徑最長。通過以上分析，多費(fèi)馬點(diǎn)鏈算法可以有效地保證將數(shù)據(jù)傳輸?shù)侥繕?biāo)區(qū)域，其數(shù)據(jù)成功傳輸比率高且穩(wěn)定。

圖6 數(shù)據(jù)包成功傳輸比率

圖7 端到端的平均延遲

圖7展示了端到端的平均延遲。簡(jiǎn)單區(qū)域鏈算法的延遲明顯高于其它3種算法，當(dāng)區(qū)域數(shù)量為16時(shí)，平均延遲為150 ms，是其它3種算法的300% ～500%;而單費(fèi)馬點(diǎn)鏈算法的平均延遲高于多費(fèi)馬點(diǎn)鏈算法，目標(biāo)區(qū)域從4變化到16時(shí)，其延遲是多費(fèi)馬點(diǎn)鏈算法的200%，因?yàn)樵撍惴▎我坏膫鬏旀溌穼?dǎo)致其傳輸路徑過長;目標(biāo)區(qū)域大于10的時(shí)候，多路徑單地域群播算法的延遲比多費(fèi)馬點(diǎn)鏈算法高出30% ～40%，因?yàn)槠溲舆t主要由兩部分組成:數(shù)據(jù)傳到第1個(gè)和最后1個(gè)目標(biāo)區(qū)域的時(shí)間和事件在隊(duì)列中的等候時(shí)間，而多費(fèi)馬點(diǎn)鏈算法是在4個(gè)網(wǎng)格同時(shí)通信，因此目標(biāo)區(qū)域數(shù)量對(duì)其的影響僅為其它算法的1/4。通過以上分析，多費(fèi)馬點(diǎn)鏈算法在平均延遲上要明顯好于其它3種算法。

圖8展示了網(wǎng)絡(luò)中的平均傳輸開銷。當(dāng)區(qū)域數(shù)量為4的時(shí)候，4種算法的平均開銷基本相同，為7 kbit;區(qū)域數(shù)量大于6時(shí)，簡(jiǎn)單區(qū)域鏈算法和多路徑單地域群播算法的開銷，明顯高于基于費(fèi)馬點(diǎn)鏈的算法，目標(biāo)區(qū)域數(shù)量從10開始一直到16，其開銷比其它基于費(fèi)馬點(diǎn)鏈的算法平均高出20%～30%。因?yàn)榛谫M(fèi)馬點(diǎn)鏈的兩種算法對(duì)傳輸鏈路進(jìn)行了優(yōu)化，鏈路數(shù)要比以上兩種算法少。通過以上分析，單費(fèi)馬點(diǎn)鏈算法和多費(fèi)馬點(diǎn)鏈算法在平均傳輸開銷上明顯低于簡(jiǎn)單區(qū)域鏈算法和多路徑單地域群播算法。

圖8 平均傳輸開銷

3 結(jié)束語

多地域群播的目標(biāo)區(qū)域數(shù)量和位置均未知，這種復(fù)雜性導(dǎo)致目前無線傳感器網(wǎng)絡(luò)多地域群播算法都無法做到能量和傳輸延遲的平衡。本文提出了一種新的基于多目標(biāo)區(qū)域的多費(fèi)馬點(diǎn)鏈算法，主要思想是以源節(jié)點(diǎn)為中心將自身傳輸區(qū)域分為4個(gè)網(wǎng)格，網(wǎng)格中選取距離源節(jié)點(diǎn)最近的目標(biāo)區(qū)域的中心點(diǎn)為簇頭，并以該簇頭與目標(biāo)區(qū)域形成三角形與四邊形相結(jié)合的費(fèi)馬點(diǎn)鏈。通過仿真實(shí)驗(yàn)表明多費(fèi)馬點(diǎn)鏈算法在保持較低能量消耗的同時(shí)大大降低了傳輸延遲。

［1］ Akyildiz I F，Su W L，Sankarasubramaniam Y.A Survey on Sensor Networks［J］.Communications Magazine，2002，40(8):102－114.

［2］ Li J Y，JAnnotti J，Couto D，et al.A Scalable Location Service for Geographic Ad Hoc Routing［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，New York，2000:120－130.

［3］ Xue Y，LI B C，Nahrstedt K.A Scalable Location Management Scheme in Mobile Ad-Hoc Networks［C］//Proc.LCN 2001.26th Annual IEEE Conference，Tampa，2001:102－111.

［4］ He T，Huang C，Blum B，et al.Rangefree Localization Schemes for Large Scale Sensor Networks［C］//Proc.of the 9th Annual International Conference on Mobile Computing and Networking，2003:81－95.

［5］ Seada K，Helmy A.Rendezvous Regions:A Scalable Architecture for Service Location and Data-Centric Storage in Large-Scale Wireless Networks［C］//Parallel and Distributed Processing Symposium，Proc.18th International，2004:218－225.

［6］ Stojmenovic I，Liu D D，Jia X H.A Scalable Quorum-Based Location Service in Ad Hoc and Sensor Networks［C］//Mobile Adhoc and Sensor Systems，Vancouver，2006:489－492.

［7］ Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless Networks［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，Boston，2000:243－254.

［8］ 胥楚貴，鄧曉衡，鄒豪杰.無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略［J］.傳感技術(shù)學(xué)報(bào)，2010，23(2):256－259.

［9］ Yu F，Park S，Lee E，et al.Elastic Routing:A Novel Geographic Routing for Mobile Sinks in Wireless Sensor Networks［C］//IET The Institution of Engineering and Technology，2010，4(6):716－727.

［10］ Wang G，Wang T，Jia W，et al:Adaptive Location Updates for Mobile Sinks in Wireless Sensor Networks［J］.The Journal of supercomputing，2009，47(2):127－145.

［11］ Ko Y B，Vaidya N H.Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks［J］.Mobile Networks and Applications，2002，7(6):471－480.

［12］ Seada K，Helmy A.Efficient Geocasting with Perfect Delivery in Wireless Networks［C］//Proceedings of IEEE WCNC 2004，Atlanta，2004，4:2551－2556.

［13］張強(qiáng)，孫雨耕，劉麗萍.邊界節(jié)點(diǎn)對(duì)無線傳感器網(wǎng)絡(luò)連通性的影響［J］.傳感技術(shù)學(xué)報(bào)，2011，24(5):737－741.

［14］ Lee S H，Ko Y B.Efficient Geocasting with Multi-Target Regions in Mobile Multi-Hop Wireless Networks［C］//Wireless Networks.2010，16(5):1253－1262.