大規(guī)模無線傳感器網(wǎng)絡(luò)查詢方法——ＣＢＱＭ

摘要：提出一種適用于大規(guī)模、高查詢率而單次查詢需要傳輸?shù)臄?shù)據(jù)量很小、位置信息無關(guān)的無線傳感器網(wǎng)絡(luò)查詢方法——CBQM。該方法以小世界理論為依據(jù)，在CARD和TRANSFER協(xié)議的基礎(chǔ)上，引入了方向邊節(jié)點，改進(jìn)了contact的選擇方法，降低了協(xié)議的能耗，提高了網(wǎng)絡(luò)生命周期。通過仿真得出，在保證查詢成功率的前提下，CBQM的查詢最優(yōu)能耗與CARD相比降低了約38%，比TRANSFER降低了40%以上。

關(guān)鍵詞：路由協(xié)議；小世界；長程連接；無線傳感器網(wǎng)絡(luò)

中圖分類號：TP393．02文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)12-0333-03

查詢方法在無線傳感器網(wǎng)絡(luò)中具有非常重要的作用，同時也是非常具有挑戰(zhàn)性的問題。許多重要的無線傳感器網(wǎng)絡(luò)路由協(xié)議是基于查詢的，如directed diffusion、TRANSFER和rumor等。本文提出了一種基于小世界理論^[1~3]的無線傳感器網(wǎng)絡(luò)查詢方法——CBQM。該方法適用于大規(guī)模、位置信息無關(guān)、高查詢率而單次查詢需要傳輸?shù)臄?shù)據(jù)量很小的無線傳感器網(wǎng)絡(luò)。CBQM方法著眼于降低路由建立的能量消耗，尋找可行的路徑，而不是最優(yōu)路徑。由此降低單次查詢的總能耗，進(jìn)而提高網(wǎng)絡(luò)的生命周期。

1相關(guān)工作

小世界理論表明，在規(guī)則網(wǎng)絡(luò)中隨機加入少量的長程連接（shortcuts），將大大地降低網(wǎng)絡(luò)直徑。基于該理論，許多研究人員在無線傳感器網(wǎng)絡(luò)中引入長程連接，以改善網(wǎng)絡(luò)的查詢性能。例如：Sharma在網(wǎng)絡(luò)中引入了有線長程連接^[4]。2002年，美國加州大學(xué)洛杉磯分校的Ahmed Helmy教授提出Ad hoc網(wǎng)絡(luò)的各個節(jié)點不僅維護(hù)鄰居節(jié)點的狀態(tài)，而且還選擇維護(hù)少數(shù)較遠(yuǎn)節(jié)點的狀態(tài)，這些較遠(yuǎn)的節(jié)點叫做contact^[5]。Contact就是網(wǎng)絡(luò)中的長程連接，它使得網(wǎng)絡(luò)成為一個小世界，大大降低了查詢源與目標(biāo)的分離度。隨后，針對不同的contact選擇方法，又設(shè)計出了CARD^[6，7]、MARQ^[8]和TRANSFER^[9]協(xié)議。MARQ主要是針對移動性較強的Ad hoc網(wǎng)絡(luò)，這里不作探討。CARD采用邊方法（EM）或概率方法（PM）來預(yù)先選擇contact^[6]，而后通過周期性發(fā)送validate的方式維護(hù)contact；而TRANSFER協(xié)議則采用動態(tài)的方式創(chuàng)建contact。當(dāng)查詢開始后，查詢信息到達(dá)某個節(jié)點時，由該節(jié)點判斷，如果必要，才開始創(chuàng)建contact^[9]。CARD架構(gòu)增加了contact的維護(hù)開銷；TRANSFER協(xié)議不需要維護(hù)contact，它在開始查詢后才按需創(chuàng)建contact，因此增加了查詢延遲，同時也增加了多次創(chuàng)建contact而帶來的能耗。

本文提出的CBQM將在CARD和TRANSFER的基礎(chǔ)上，改進(jìn)contact創(chuàng)建方法，目的是降低協(xié)議的查詢能耗。

2CBQM查詢方法

CBQM查詢方法主要包括鄰居維護(hù)、contact選擇與維護(hù)、查詢?nèi)齻€環(huán)節(jié)。

2．1相關(guān)定義

文中的相關(guān)定義基本沿用文獻(xiàn)[6]中的相關(guān)定義，如圖1所示。

1）節(jié)點的鄰居位于該節(jié)點周圍R跳以內(nèi)的所有節(jié)點，其中R≥1是正整數(shù)，一般取值不會太大；恰好位于該節(jié)點周圍R跳上的鄰居，叫做邊節(jié)點E。

2）Contact距離rContact距離源節(jié)點的限制跳數(shù)，為了避免重疊，令r≥2R。

3）最大contact數(shù)量NoC每個節(jié)點可以選擇contact的最大數(shù)量。

4）搜索深度D源節(jié)點查詢contact的級數(shù)（contact的contact）。

2．2創(chuàng)建并維護(hù)鄰居和contact狀態(tài)

圖5比較了CBQM和CARD在鄰居建立和contact建立階段的數(shù)據(jù)包流量曲線，間接反映了能耗（數(shù)據(jù)包流量越大，網(wǎng)絡(luò)能耗越大）。實驗網(wǎng)絡(luò)節(jié)點數(shù)是200。如圖5所示，在30 s之前，CBQM和CARD都出現(xiàn)了流量峰值，這是由于在鄰居建立是采用泛洪的方法，造成了大量的數(shù)據(jù)包流量；30 s之后是contact建立階段，該階段CBQM較CARD節(jié)省50%左右的能耗。

圖6顯示在不同規(guī)模的網(wǎng)絡(luò)中，CBQM單次查詢的平均能耗相比CARD、TRANSFER和flood都優(yōu)越，并且隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，CBQM的性能體現(xiàn)得更加明顯。實驗表明，在保證查詢成功率的前提下，CBQM的單次查詢平均最優(yōu)能耗比CARD低38%左右（5 000節(jié)點時），而比TRANSFER低40%以上。

4結(jié)束語

本文提出了一種無線傳感器網(wǎng)絡(luò)查詢、資源發(fā)現(xiàn)方法—CBQM。它在CARD架構(gòu)的基礎(chǔ)上，改進(jìn)了contact的選擇方法。通過仿真實驗表明，CBQM在能耗方面具有非常優(yōu)越的表現(xiàn)。

參考文獻(xiàn)：

[1]WATTS D J，STROGATZ S H.Collective dynamics of small－world networks[J].Nature，1998，393(6)：440-442.

[2]NEWMAN M E J，WATTS D J.Scaling and percolation in the small－world network model[J].Phys Rev E，1999，60(2):7332-7342.

[3]NEWMAN M E J. Models of the small world[J]. J Stat Phys，2000，101:819-841.

[4]SHARMAG，MAZUMDAR R.Hybrid sensor networks: a small world[C]//Proc of the 6th ACM International Symposium on Mobile Ad hoc Networking and Computing. 2005:366-377.

[5]HELMY A.Architectural framework for large－scale multicast in mobile Ad hoc networks[C]//IEEE International Conference on Communications(ICC 2002). 2002:2036-2042.

[6]HELMY A，GARG S，PAMU P，et al.Contact based architecture for resource discovery (CARD) in large scale MANETS[C]//IEEE ACM IPDPS Int’l Workshop on Wireless， Mobile and Ad hoc Networks(WMAN). 2003:219-227.

[7]HELMY A，GARG S，PAMU P，et al.CARD: a contact－based architecture for resource discovery in Ad hoc networks[J].MONET Journal，2005，10:99－113.

[8]HELMY A.Mobility－assisted resolution of queries in large－scale mobile sensor networks (MARQ)[J]. Computer Networks Journal: Elsevier Science， 2003，43(4):437-458.

[9]HELMY A.TRANSFER: transactions routing for Ad hoc networks with efficient energy[C]//Proc of IEEE GLOBECOM. 2003:398-404.

[10]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D，et al.Directed diffusion for wireless sensor networking[J].IEEE/ACM Trans on Networking，2003，11(1):2－16.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”