分裂無線傳感器網(wǎng)絡(luò)路由協(xié)議綜述

袁婧

[摘 要]無線傳感器網(wǎng)絡(luò)中,由于節(jié)點(diǎn)能量與通信距離的限制以及節(jié)點(diǎn)受到惡劣天氣與環(huán)境變化等因素的影響,節(jié)點(diǎn)間的通信會(huì)出現(xiàn)間隔性,甚至直接導(dǎo)致分裂網(wǎng)絡(luò)的產(chǎn)生。本文在介紹分裂無線傳感器網(wǎng)絡(luò)的基礎(chǔ)上,對(duì)解決分裂網(wǎng)絡(luò)節(jié)點(diǎn)或區(qū)域間通信問題的路由算法進(jìn)行了綜述,著重介紹了一些具有代表性的路由協(xié)議。

[關(guān)鍵詞]無線傳感器網(wǎng)絡(luò) 網(wǎng)絡(luò)分裂 路由協(xié)議

引言

隨著傳感技術(shù)、微機(jī)電系統(tǒng)、無線通信等各類技術(shù)的進(jìn)步,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)也得到快速發(fā)展。無線傳感器網(wǎng)絡(luò)是由成千上萬個(gè)微小傳感器節(jié)點(diǎn)所組成的一種特殊的無線自組織網(wǎng)絡(luò)(Ad hoc網(wǎng)絡(luò))[1]。這些體積微小的傳感器具有傳感、數(shù)據(jù)處理和短距離無線通信等多種功能,可以輕松的實(shí)時(shí)監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對(duì)象的信息。無線傳感器網(wǎng)絡(luò)擴(kuò)展了人們的信息獲取能力,為人們提供最直接、最有效、最真實(shí)的信息[2]。無線傳感器網(wǎng)絡(luò)的應(yīng)用前景非常廣泛,目前主要運(yùn)用在國防軍事、環(huán)境監(jiān)測、城市交通、空間探索、智能家居、災(zāi)難救援等多個(gè)領(lǐng)域。

一、分裂無線傳感器網(wǎng)絡(luò)路由協(xié)議

理想的無線傳感器網(wǎng)絡(luò)應(yīng)當(dāng)是所有節(jié)點(diǎn)都處于可連通的狀態(tài),大部分經(jīng)典路由算法也是基于這一假設(shè)所提出的。但是當(dāng)無線傳感器網(wǎng)絡(luò)投入到實(shí)際應(yīng)用中之后,由于傳感節(jié)點(diǎn)的能量和通信距離的限制、以及受到惡劣天氣與環(huán)境等其它因素的影響,節(jié)點(diǎn)間的通信會(huì)出現(xiàn)間隔性,導(dǎo)致網(wǎng)絡(luò)間斷性連通,或者直接導(dǎo)致分裂網(wǎng)絡(luò)的產(chǎn)生。所謂分裂網(wǎng)絡(luò)就是指一個(gè)網(wǎng)絡(luò)由于某種原因被迫分裂為兩個(gè)或兩個(gè)以上相互間無法通信的子網(wǎng)絡(luò),某一子網(wǎng)中的任一節(jié)點(diǎn)都無法與另一子網(wǎng)中的節(jié)點(diǎn)交換信息。適用于分裂無線傳感器網(wǎng)絡(luò)的路由協(xié)議所要解決的問題就是在網(wǎng)絡(luò)的正常通信因?yàn)橐恍┰虮蛔钄嗟那闆r下找到合適的傳輸路徑,以便有效地將報(bào)文傳送到目的地。

(一)基于消息復(fù)制的路由協(xié)議

這類路由算法的主要思想就是在網(wǎng)絡(luò)中出現(xiàn)通信機(jī)會(huì)時(shí)采用信息復(fù)制的方式來轉(zhuǎn)發(fā)數(shù)據(jù)包。當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包到某個(gè)無直接通信鏈路的目的節(jié)點(diǎn)時(shí),它會(huì)復(fù)制多個(gè)副本傳送給它的鄰居節(jié)點(diǎn)。這種路由策略通過提高數(shù)據(jù)包的冗余度來增加端到端傳輸?shù)某晒Ω怕?降低傳輸延遲時(shí)間。傳染路由算法(Epidemic Routing)[3]和Spray-and-Wait算法[4]是最具代表性的基于洪泛方式的路由算法。

傳染路由算法引入了同步復(fù)制數(shù)據(jù)庫的技術(shù)來解決間斷性連通網(wǎng)絡(luò)的路由問題。算法規(guī)定網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)相遇時(shí)都相互交換各自攜帶的信息。用這種路由策略傳輸信息的好處是完全不需要預(yù)知網(wǎng)絡(luò)的拓?fù)湫畔?就可確保信息到達(dá)目的節(jié)點(diǎn),但是由于一些不必要的信息復(fù)制,大量的網(wǎng)絡(luò)資源被浪費(fèi)。Spray-and-Wait算法對(duì)傳染路由算法進(jìn)行了改進(jìn),它預(yù)先限定網(wǎng)絡(luò)中的報(bào)文副本數(shù)量,在傳輸過程中只進(jìn)行有限次的復(fù)制,提高了網(wǎng)絡(luò)資源的利用率。Spray-and-Wait算法主要包括數(shù)據(jù)包的“噴灑”(spray)和“等待”(wait)兩個(gè)階段。

(二)基于節(jié)點(diǎn)移動(dòng)的路由協(xié)議

這類路由策略通常在網(wǎng)絡(luò)中設(shè)置個(gè)別可以主動(dòng)移動(dòng)的特殊節(jié)點(diǎn),這些特殊節(jié)點(diǎn)可以控制自身的移動(dòng)方向和速度,按照預(yù)定的路線在互相無法通信的節(jié)點(diǎn)或區(qū)域間移動(dòng),以“存儲(chǔ)攜帶轉(zhuǎn)發(fā)”的報(bào)文傳輸模式工作。近年來,國內(nèi)外學(xué)者在將可管理的移動(dòng)節(jié)點(diǎn)引入分裂網(wǎng)絡(luò)以實(shí)現(xiàn)數(shù)據(jù)匯集這一類路由算法上作了一些有益的探索。其中具有代表性的是信息擺渡算法(Message Ferrying)[6]和信息數(shù)據(jù)騾(Data Mules)算法。

Wenrui Zhao等人在文獻(xiàn)[5]中提出的“信息擺渡”方法將可控制的擺渡節(jié)點(diǎn)(ferry)引入高分裂網(wǎng)絡(luò)之中,在節(jié)點(diǎn)固定情況下,ferry按固定路線勻速行走為節(jié)點(diǎn)間提供正常的通信。文獻(xiàn)[6]提出了節(jié)點(diǎn)主動(dòng)MF方案(NIMF)和ferry主動(dòng)MF方案(FIMF)兩種機(jī)制來控制該擺渡節(jié)點(diǎn)的移動(dòng)路線,協(xié)助報(bào)文傳輸。文獻(xiàn)[7]考慮了多個(gè)擺渡節(jié)點(diǎn)的網(wǎng)絡(luò),以滿足流量需求且傳輸延遲最小為優(yōu)化目標(biāo),提出了計(jì)算擺渡節(jié)點(diǎn)最優(yōu)移動(dòng)路線的算法。文獻(xiàn)[8]則提出了一個(gè)被稱為OPWP(optimized way-point)的擺渡節(jié)點(diǎn)路由算法,不需要擺渡節(jié)點(diǎn)與其他普通節(jié)點(diǎn)進(jìn)行任何的在線合作即可確定其路由。文獻(xiàn)[9]將消息擺渡模式引入無線傳感器網(wǎng)絡(luò),利用ferry來收集分區(qū)緩存信息,其主要研究內(nèi)容是通過采用節(jié)能方法讓節(jié)點(diǎn)經(jīng)濟(jì)使用電池以延長網(wǎng)絡(luò)生存時(shí)間。

二、結(jié)束語

對(duì)分裂無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究尚處于起步階段,其中仍有許多的問題和挑戰(zhàn)等待解決。通過對(duì)現(xiàn)有成果的分析和總結(jié),我們可以認(rèn)為未來的研究熱點(diǎn)和趨勢:(1)復(fù)制策略將往智能復(fù)制方向發(fā)展,有選擇的復(fù)制傳輸,從而提高網(wǎng)絡(luò)資源的利用率。(2)Ferry路線的優(yōu)化、多ferry路由設(shè)計(jì)等方面都將成為信息擺渡策略研究領(lǐng)域的熱點(diǎn)。

參考文獻(xiàn)

[1]D Estrin, R Govindan, J Heidemann。Next century challenges: scalable coordination in sensor networks[A]Proceedings of the 5th annual ACM/IEEE international Conference on Mobile Computing and network [C] NY,USA:ACM Press,1999, 263-270

[2]孫利民,李建中,陳渝等。無線傳感器網(wǎng)絡(luò)[M]北京:清華大學(xué)出版社, 2005

[3]Vahdat A, Becker D。Epidemic routing for partially connected ad hoc networks[J]CS-2000-06[R]Durham, NC: Duke University 2000

[4]Spyropoulos T, Psounis K。Raghavendra C S. Spray and wait: An efficient routing scheme for intermittently connected mobile networks[A]//Proc of the ACM SIGCOMM Workshop on Delay-Tolerant Networking(WDTN 2005)[C] New York: ACM, 2005,pp: 252-259

[5]Wenrui Zhao, Ammar M.H. Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks[A]The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems, 2003[C]FTDCS 2003. Proceedingspp:308314, 28-30 May 2003

[6]Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc Networks[A]//Proc of the ACM MOBIHOC[C] New York: ACM, 2004,pp:187-19

[7]Zhao W, Ammar M, Zegura E. Controlling the mobility of multiple data transport ferries in a delay-tolerant network[A]//Proc of the IEEE INFOCOM. Piscataway[C], NJ:IEEE, 2005, pp:1407-1418

[8]Tariq M M B, Ammar M, Zegura E. Message ferry route design for sparse ad hoc networks with mobile nodes[A]//Proc of the ACM MOBIHOC 2006[C] New York: ACM, 2006,pp:37-48

[9]Yi-hua Zhu, Wan-deng Wu, Victor C.M. Leung. Energy-efficient Tree-based Message Ferrying Routing Schemes for Wireless Sensor Networks [J] Mobile Networks and Applications (in press)