基于內(nèi)容尋址的無線傳感器網(wǎng)絡(luò)路由協(xié)議

張麗娟，陳志奎

(大連理工大學(xué)軟件學(xué)院 遼寧 大連 116620)

基于內(nèi)容尋址的無線傳感器網(wǎng)絡(luò)路由協(xié)議

張麗娟，陳志奎

(大連理工大學(xué)軟件學(xué)院 遼寧 大連 116620)

提出了一種基于內(nèi)容尋址的無線傳感器網(wǎng)絡(luò)路由協(xié)議——CAWSN路由協(xié)議。將有線P2P網(wǎng)絡(luò)的結(jié)構(gòu)化分布式哈希表(DHT)思想與CAN算法引入到了無線傳感器網(wǎng)絡(luò)，使節(jié)點之間以廣播的方式直接進行信息交互，共同完成感知任務(wù)，減少了單一節(jié)點工作量。通過ns2網(wǎng)絡(luò)模擬實驗平臺對該協(xié)議進行大量仿真實驗，驗證了CAWSN路由協(xié)議對無線傳感器網(wǎng)絡(luò)性能的提高具有重要意義。

CAN算法; DHT; ns2; P2P路由協(xié)議; 無線傳感器網(wǎng)絡(luò)

近年來，由于無線傳感器網(wǎng)絡(luò)在醫(yī)療護理、軍事領(lǐng)域、環(huán)境檢測等領(lǐng)域有了重要的應(yīng)用，所以受到了越來越多人的關(guān)注。傳統(tǒng)的無線傳感器網(wǎng)絡(luò)，消息通過多跳的方式轉(zhuǎn)發(fā)到中心服務(wù)器(C/S模式)，常導(dǎo)致網(wǎng)絡(luò)擁塞、耗電量快、資源浪費、節(jié)點易失效，從而使網(wǎng)絡(luò)變得不穩(wěn)定、效率低甚至不可用[1]。針對這一問題，本文提出了一種基于內(nèi)容尋址的無線傳感器網(wǎng)絡(luò)路由協(xié)議(CAWSN)，引入了CAN路由協(xié)議中的確定鄰居節(jié)點的方法，并讓傳感器節(jié)點只與其鄰居節(jié)點直接進行信息交互，形成小范圍的P2P網(wǎng)絡(luò)，共同完成感知任務(wù)。本文通過ns2網(wǎng)絡(luò)模擬平臺，對不同數(shù)目的節(jié)點分別進行C/S模式、P2P模式、CAWSN模式通信，并從網(wǎng)絡(luò)吞吐量、網(wǎng)絡(luò)延時、網(wǎng)絡(luò)抖動率方面對這3種路由形式進行了比較，得出了CAWSN路由協(xié)議可以有效查找鄰居節(jié)點，并使WSN網(wǎng)絡(luò)更加穩(wěn)定、高效的結(jié)果。

1 國內(nèi)外研究現(xiàn)狀

無線傳感器網(wǎng)絡(luò)中，引入P2P思想，受到了國內(nèi)外研究者的重視。文獻[2]對WSN中以P2P方式能更清晰準確地感知目標(biāo)事物進行了研究。文獻[3]介紹了無線傳感器網(wǎng)絡(luò)如何以P2P方式聯(lián)網(wǎng)構(gòu)建移動的小型P2P傳感器網(wǎng)絡(luò)。文獻[4]提出了P2P管道時間切分模型，并給出了P2PWSNDAS體系結(jié)構(gòu)。文獻[5]基于WSN和P2P網(wǎng)絡(luò)特點，提出了ITS網(wǎng)絡(luò)體系結(jié)構(gòu)。文獻[6]介紹了無線傳感器網(wǎng)絡(luò)中P2P算法原理。它們都從不同的方面將P2P思想與WSN網(wǎng)絡(luò)結(jié)合起來，從而提高WSN網(wǎng)絡(luò)性能。本文將進一步研究P2PWSN路由協(xié)議。

2 P2P對等網(wǎng)絡(luò)與無線傳感器網(wǎng)絡(luò)

P2P網(wǎng)絡(luò)是為了完成感知任務(wù)，節(jié)點與節(jié)點之間直接進行數(shù)據(jù)傳輸、資源共享、協(xié)同工作的雙向互動過程。每個節(jié)點與其周圍的鄰居節(jié)點形成小范圍內(nèi)的網(wǎng)絡(luò)系統(tǒng)，因為每個節(jié)點都是對等的，所以如果一個節(jié)點失效，不會影響整個系統(tǒng)[7]，非常適用于節(jié)點易失效的傳感器網(wǎng)絡(luò)。并且由于傳感器節(jié)點體積小、計算能力有限、電池儲備少，要完成一項感知任務(wù)，最好是多個節(jié)點協(xié)同工作，從而減少單一節(jié)點工作量，使感知工作更加準確、高效，所以引入P2P思想對WSN網(wǎng)絡(luò)來說具有重要的意義。

3 CAWSN路由協(xié)議

3.1 對等無線傳感器網(wǎng)絡(luò)的實現(xiàn)

為了使傳感器中的每個節(jié)點處于對等位置，即可以相互交換信息，需要使對等網(wǎng)絡(luò)中每個節(jié)點擁有一個相同并且最新的全局狀態(tài)變量 。根據(jù)凸函數(shù)最優(yōu)解原理[8]，通過計算凸函數(shù)得到的局部最優(yōu)解，也為全局(整個網(wǎng)絡(luò))的最優(yōu)解。所以對于WSN網(wǎng)絡(luò)，主要任務(wù)就是求得該最優(yōu)解。

估量最優(yōu)解的求解過程如下：

其次是網(wǎng)絡(luò)拓撲圖的構(gòu)成：分布式散列表的邏輯視圖映射到真實視圖(后文詳細介紹)后，再經(jīng)式(3)計算下一跳鄰居節(jié)點：

由此產(chǎn)生的網(wǎng)絡(luò)拓撲如圖1所示。

圖1 網(wǎng)絡(luò)拓撲圖

該網(wǎng)絡(luò)拓撲實質(zhì)為一條馬爾科夫鏈[10]，它是一種狀態(tài)序列，其下一狀態(tài)值取決于當(dāng)前網(wǎng)絡(luò)狀態(tài)。

3.2 分布式散列表DHT

P2P網(wǎng)絡(luò)也可以說是節(jié)點與其鄰居節(jié)點直接進行信息處理的網(wǎng)絡(luò)，那么鄰居節(jié)點的發(fā)現(xiàn)就顯得非常重要。對于鄰居節(jié)點的發(fā)現(xiàn)機制，本文采用的是分布式散列表方法[11]，即：對節(jié)點如何進行內(nèi)部管理并分割它們的地址空間，使每個節(jié)點只存儲其若干個鄰居節(jié)點的信息。分布式散列表中的地址空間由巨大的數(shù)值組成，如范圍為0～ (2160?1)。對地址空間上的所有元素數(shù)量執(zhí)行取模，從而產(chǎn)生的環(huán)狀拓撲如圖2所示。

圖2 地址空間操作示意圖

圖中給出了分布式散列表的邏輯視圖映射到真實拓撲的示意圖?？梢钥闯鏊菍⒌乩砦恢眯畔⑥D(zhuǎn)換為簡單的數(shù)學(xué)拓撲。

3.3 鄰居節(jié)點發(fā)現(xiàn)機制

當(dāng)節(jié)點信息的地理位置映射為邏輯拓撲后，需要繼續(xù)確定節(jié)點的鄰居節(jié)點。本文主要借鑒了有線P2P網(wǎng)絡(luò)中的基于內(nèi)容尋址路由協(xié)議(CAN)。在CAN中定位對象和路由消息是非常簡單的，因為它僅需要關(guān)于一個節(jié)點直接鄰居的信息，但是CAN引入了多維標(biāo)識符空間的概念，與單維空間中線性遍歷相比，路由效率得到了極大的提高[12]。一個CAN標(biāo)識符空間能夠看作是一個Chord或Pastry標(biāo)識符空間的l維版本。標(biāo)識符空間每一維中在標(biāo)識符上的所有算術(shù)運算對最大坐標(biāo)執(zhí)行取模，本文采取的是對網(wǎng)絡(luò)中節(jié)點數(shù)N進行取模運算。如果l維空間中兩個節(jié)點的坐標(biāo)在一個維度內(nèi)重疊，并在其他l?1維中相鄰，則這兩個節(jié)點被認為是鄰居，如圖3所示。

圖3 鄰居節(jié)點示意圖

圖中，節(jié)點N2和N6是鄰居，因為它們在x維重疊，并在y維相互鄰接。同時，N5和N6不是鄰居，因為它們不在任一維內(nèi)重疊。而N2和N3在y維重疊，但在x維不相鄰，所以它們不是鄰居(注意以上操作是針對傳感器節(jié)點地理信息取模后進行的)。在一個l維的標(biāo)識符空間中，標(biāo)識符空間被分割成大小相等的區(qū)，每個節(jié)點便具有了2l個鄰居。因此，參與到一個CAN系統(tǒng)中的節(jié)點數(shù)量能夠增長至巨大，而每個節(jié)點的必要鄰居節(jié)點路由信息則保持為常數(shù)。

對于無線傳感器網(wǎng)絡(luò)中失效離開的節(jié)點，本文對節(jié)點間的通信設(shè)置檢查超時，更新鄰居指針表，從而確保故障節(jié)點從指針表中被去除。因為網(wǎng)絡(luò)中節(jié)點是對等的，沒有節(jié)點扮演不同角色，一個節(jié)點的離開或特意去除不會對DHT的功能產(chǎn)生明顯影響，因此對于隨機性故障和攻擊，分布式散列表被認為是非常魯棒的。改進的CAN算法選擇鄰居節(jié)點的方式采用了節(jié)點間直接通信(P2P)模式，但其鄰居節(jié)點的確定是隨機任意指定的，本文稱為RP2P模式。CAWSN模式更準確、穩(wěn)定，下面的仿真實驗驗證了這一結(jié)論。

4 仿真實驗

本文實驗是在網(wǎng)絡(luò)仿真平臺ns2[13]上實現(xiàn)的。程序語言由C++、Otcl腳本共同完成。實驗設(shè)置了5、10、25個節(jié)點的無線場景，它們分別以C/S模式、RP2P模式、CAWSN模式進行數(shù)據(jù)交換，并從網(wǎng)絡(luò)延時、網(wǎng)絡(luò)抖動率(衡量網(wǎng)絡(luò)穩(wěn)定性)、網(wǎng)絡(luò)吞吐量對網(wǎng)絡(luò)性能的影響進行比較。圖4為CAWSN模式的nam文件在某一時刻截取到的運行場景圖。

圖4 CAWSN模式運行圖

如圖5可知，RP2P與CAWSN網(wǎng)絡(luò)的網(wǎng)絡(luò)延時都只有0.019 s左右，CAWSN比RP2P延時略大0.002 s，這是因為CAWSN在計算鄰居節(jié)點時需要有少量計算而耗時，但因為都已經(jīng)特別小，可忽略不計。

圖5 RP2P與CAWSN網(wǎng)絡(luò)延時比較圖

由于C/S模式常造成消息排隊等待，所以網(wǎng)絡(luò)延時大。由圖6可知，C/S模式網(wǎng)絡(luò)平均延時為1.3 s，是RP2P、CAWSN方式的50倍左右。

圖6 C/S網(wǎng)絡(luò)延時示意圖

CAWSN模式借鑒了CAN路由算法，所以較隨機發(fā)現(xiàn)鄰居節(jié)點方式更穩(wěn)定。由圖7可知，CAWSN網(wǎng)絡(luò)抖動率比RP2P抖動率小，充分說明了CAWSN網(wǎng)絡(luò)確實更加穩(wěn)定。

圖7 RP2P與CAWSN網(wǎng)絡(luò)抖動率比較圖

由圖8可知，C/S模式抖動率比RP2P模式、CAWSN模式小，說明C/S網(wǎng)絡(luò)穩(wěn)定，這是由于P2P網(wǎng)絡(luò)及C/S網(wǎng)絡(luò)各自的特點決定的。

圖8 C/S網(wǎng)絡(luò)抖動率示意圖

當(dāng)節(jié)點數(shù)目少時，C/S模式的網(wǎng)絡(luò)吞吐量會略大。由圖9可知，10個節(jié)點時，C/S吞吐量大于CAWSN模式，略大于RP2P模式。

圖9 RP2P、CAWSN、C/S網(wǎng)絡(luò)吞吐量比較圖

當(dāng)節(jié)點數(shù)設(shè)為5、10、25個時，分別以C/S模式、RP2P模式、CAWSN模式進行通信，通過27組仿真實驗，得到的網(wǎng)絡(luò)延時、網(wǎng)絡(luò)抖動率、網(wǎng)絡(luò)吞吐量等相關(guān)數(shù)據(jù)如表1～表3所示。

表1 C/S、RP2P、CAWSN網(wǎng)絡(luò)吞吐量比較

由表1可知，當(dāng)節(jié)點數(shù)增加時，C/S模式吞吐量會逐漸減少，這是由于節(jié)點數(shù)增加時，導(dǎo)致了更多的節(jié)點向中心節(jié)點發(fā)送數(shù)據(jù)時需要排隊等待。而RP2P和CAWSN模式隨節(jié)點增多而逐漸增加，并且CAWSN網(wǎng)絡(luò)吞吐量總是大于RP2P模式，這是由于節(jié)點之間直接進行數(shù)據(jù)傳輸，節(jié)點數(shù)越多，某一時刻網(wǎng)絡(luò)吞吐量也隨之增加。

表2 C/S、RP2P、CAWSN網(wǎng)絡(luò)延時比較

由表2數(shù)據(jù)可知，當(dāng)節(jié)點數(shù)增多時，網(wǎng)絡(luò)延時均會增加，但RP2P模式和CAWSN模式始終遠小于C/S模式，這是由于C/S模式消息等待排隊的結(jié)果。而CAWSN略大于RP2P，這是由于CAWSN模式需要一定的計算量。

表3 C/S、RP2P、CAWSN網(wǎng)絡(luò)抖動率比較

由表3可知，當(dāng)節(jié)點數(shù)增加后，CAWSN、RP2P模式網(wǎng)絡(luò)抖動率逐漸減少，而C/S模式抖動率增加，由此說明C/S模式當(dāng)節(jié)點數(shù)量增多后，網(wǎng)絡(luò)變得越來越不穩(wěn)定。相反CAWSN、RP2P網(wǎng)絡(luò)卻變得越來越穩(wěn)定，并且CAWSN的抖動總小于RP2P模式，說明了CAWSN模式要比RP2P模式穩(wěn)定。

綜上所述，對于節(jié)點數(shù)目龐大的無線傳感器網(wǎng)絡(luò)，將P2P思想引入無線傳感器網(wǎng)絡(luò)后，能夠有效地提高網(wǎng)絡(luò)性能、降低網(wǎng)絡(luò)延時、增強數(shù)據(jù)傳輸效率。

5 結(jié) 束 語

本文對基于內(nèi)容尋址的無線傳感器網(wǎng)絡(luò)路由協(xié)議進行了深入研究，介紹了如何實現(xiàn)P2P無線傳感器網(wǎng)絡(luò)，并且對鄰居節(jié)點的發(fā)現(xiàn)機制借鑒了CAN路由協(xié)議，通過網(wǎng)絡(luò)模擬平臺ns2對C/S模式、RP2P模式、CAWSN模式分別進行了仿真實驗，比較網(wǎng)絡(luò)延時、抖動率、吞吐量3方面，得知了CAWSN更適合數(shù)量龐大的傳感器網(wǎng)絡(luò)，可以有效提高網(wǎng)絡(luò)性能。而對于如何將P2P思想全面應(yīng)用于無線傳感器網(wǎng)絡(luò)的各個方面，如數(shù)據(jù)分布式對等存儲、資源共享、目標(biāo)探測等，還有待于進一步的研究。

[1] RONDINI E, HAILES S, LI L. Load sharing and bandwidth control in mobile P2P wireless sensor networks[C]//Sixth Annual IEEE International Conference on Pervasive Computing and Communications. [S.l.]: IEEE, 2008,468-473.

[2] XUE W, SHENG W, DAO W B, et al. Distributed peer-to-peer target tracking in wireless sensor networks[J].Sensors, 2007, 7(6): 1001-1027.

[3] 崔瑞瑞, 莊 雷. 基于P2P的小型無線傳感器網(wǎng)絡(luò)的研究[J]. 傳感技術(shù)學(xué)報, 2006, 19(3): 900-904.

CUI Rui-rui, ZHUANG Lei. Research of small-scale wireless sensor networks based on peer-to-peer[J]. Chinese Journal of Sensors and Actuators, 2006, 19(3): 900-904.

[4] SASTRY C, MA C, LOIACONO M, et al. Peer-to-peer wireless sensor network system data acquisition system with pipelined time division scheduling[C]//Sarnoff Symposium,IEEE, 2006. Princeton, NJ, USA: IEEE, 2006: 1-4.

[5] LI Li, LIU Yuan-an, TANG Bi-hua. An intelligent transportation system network architecture based on WSN and P2P network[J]. The Journal of China University of Posts and Telecommunications, 2007, 14(1): 65-70.

[6] CARRETTI C M. Comparison of distributed optimization algorithms in sensor networks[M]. Stockholm, Sweden:Royal Institute of Technology (KTH), 2008.

[7] 李娟娟, 錢德沛, 仝 杰, 等. 基于P2P 的無線傳感器網(wǎng)絡(luò)應(yīng)用架構(gòu)研究[J]. 微電子學(xué)與計算機, 2006, 23(9):13-19.

LI Juan-juan, QIAN De-pei, TONG-Jie, et al. A P2P-based application architecture for wireless sensor networks[J].Microelectronics & Computer, 2006, 23(9): 13-19.

[8] BOYD S, VANDENBERGHE L. Convex optimization[M].Cambridge UK: Cambridge University Press, 2004.

[9] JOHANSSON B, CARRETTI C M, JOHANSSON M. On distributed optimization using peer-to-peer communications in wireless sensor networks[C]//Proceedings of IEEE SECON. [S.l.]: IEEE, 2008: 497-505.

[10] BOYD S, DIACONIS P, XIAO L. Fastest mixing Markov chain on a graph[J]. SIAM Rev, 2004, 46: 667-689.

[11] RALF S, KLAUS W. P2P系統(tǒng)及其應(yīng)用[M]. 王玲芳, 陳焱, 譯. 北京: 機械工業(yè)出版社, 2008.

RALF S, KLAUS W. Peer-to-peer systems and applications[M]. Translated by WANG Ling-fang, CHEN Yan. Beijing: China Machine Press, 2008.

[12] RATNASAMY S, FRANCIS P, HANDLEY M, et al. A scalable content addressable network[C]//Proceedings of the 2001 SIGCOMM conference. Berkeley: ACM, 2001,31(4): 161-172.

[13] KEVIN F, KANNAN V. The ns manual[M]. Berkeley:LBL, USC/ISI, and Xerox PARC, 2002.

Content Addressing Routing Protocol for Wireless Sensor Networks

ZHANG Li-juan and CHEN Zhi-kui

(School of Software, Dalian University of Technology Dalian Liaoning 116620)

A content address for wireless sensor networks (CAWSN) routing protocol is put forward in this paper. Adding both P2P structured distributing hash table and CAN algorithm to wireless sensor networks makes the nodes exchange information directly in the way of broadcasting and complete the perception task together so as to reduce the work of a single node. Finally, the experiments of simulation based on the ns2 verify that CAWSN Routing Protocol has the important effect on the improvement of functionality of wireless sensor networks.

content addressable network algorithm; distributed Hash table; ns2; P2P routing protocol;wireless sensor networks

TN92

A

10.3969/j.issn.1001-0548.2010.z1.027

2009 ? 11 ? 25

張麗娟(1984 ? )，女，碩士生，主要從事P2P無線傳感器網(wǎng)絡(luò)方面的研究.

編 輯 漆 蓉