汪 芳,張?jiān)朴?房秉毅

（中國(guó)聯(lián)通集團(tuán)研究院 北京 100048）

1 引言

近年來(lái)，隨著無(wú)線通信技術(shù)和傳感器終端設(shè)備的發(fā)展，傳感器網(wǎng)絡(luò)得到了較為廣泛的應(yīng)用。然而，設(shè)備的多樣性和不穩(wěn)定性、網(wǎng)絡(luò)的動(dòng)態(tài)性以及數(shù)據(jù)的密集性等特點(diǎn)給傳感器網(wǎng)絡(luò)的開(kāi)發(fā)帶來(lái)了各種挑戰(zhàn)，尤其是針對(duì)傳感器網(wǎng)絡(luò)的數(shù)據(jù)查詢和網(wǎng)絡(luò)協(xié)議的開(kāi)發(fā)。

傳感器網(wǎng)絡(luò)開(kāi)發(fā)的一個(gè)瓶頸是缺乏編程抽象，這引起學(xué)術(shù)界和工業(yè)界的廣泛重視。歐盟“傳感器網(wǎng)絡(luò)開(kāi)發(fā)和控制協(xié)同嵌入式系統(tǒng)”項(xiàng)目（Embedded WiSeNts）研究路線圖報(bào)告指出：“現(xiàn)在亟需一種新的高層編程模型，使抽象的層次從以系統(tǒng)為中心的編程提升到以應(yīng)用為中心的編程。用戶應(yīng)該指定預(yù)期的行為，而不是必須去處理系統(tǒng)的細(xì)節(jié)。特別地，此類模型應(yīng)支持通過(guò)對(duì)需要實(shí)現(xiàn)的功能的聲明式描述來(lái)對(duì)傳感器網(wǎng)絡(luò)的整體進(jìn)行編程，而不是針對(duì)單個(gè)節(jié)點(diǎn)的行為進(jìn)行描述[1]，從而使用戶從底層的細(xì)節(jié)中脫離出來(lái)，將注意力集中在高層的應(yīng)用邏輯上”。

在計(jì)算機(jī)技術(shù)領(lǐng)域，聲明式編程語(yǔ)言被認(rèn)為是編程語(yǔ)言的未來(lái)發(fā)展趨勢(shì)，以提供更高層抽象的編程模型[2]。數(shù)據(jù)查詢語(yǔ)言，如SQL就是一種聲明式的編程語(yǔ)言。近年來(lái)，研究人員嘗試?yán)脭?shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）對(duì)傳感器網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行管理和查詢，以簡(jiǎn)化傳感器數(shù)據(jù)密集型應(yīng)用的開(kāi)發(fā)[3,4]。此外，遞歸的Datalog語(yǔ)言可以描述圖的連通性、可達(dá)性，如生成樹(shù)和傳遞閉包等經(jīng)典的圖論問(wèn)題[5,6]。因此，研究人員嘗試?yán)肈atalog語(yǔ)言的擴(kuò)展來(lái)描述生成樹(shù)和路由等網(wǎng)絡(luò)計(jì)算問(wèn)題，以提供聲明式的網(wǎng)絡(luò)開(kāi)發(fā)模式[7,8]。本文介紹和分析聲明式傳感器網(wǎng)絡(luò)開(kāi)發(fā)模式的發(fā)展和現(xiàn)狀，并提出未來(lái)研究發(fā)展的一些建議。

2 傳感器網(wǎng)絡(luò)聲明式數(shù)據(jù)查詢處理系統(tǒng)

回顧數(shù)據(jù)庫(kù)領(lǐng)域的發(fā)展，邏輯層相對(duì)物理層的獨(dú)立是數(shù)據(jù)庫(kù)管理系統(tǒng)的基本原則。利用關(guān)系演算提供以數(shù)據(jù)為中心的應(yīng)用的抽象模型帶來(lái)關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)（RDBMS）在技術(shù)和商業(yè)上的巨大成功[9]。數(shù)據(jù)查詢語(yǔ)言SQL為數(shù)據(jù)查詢提供了聲明式的方法，使數(shù)據(jù)的查詢獨(dú)立于數(shù)據(jù)的物理表示，而讓數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)優(yōu)化和執(zhí)行。

傳感器網(wǎng)絡(luò)通過(guò)傳感器節(jié)點(diǎn)的協(xié)同工作，對(duì)地理范圍內(nèi)的對(duì)象進(jìn)行感知，采集并處理數(shù)據(jù)，并將處理結(jié)果發(fā)布給用戶。對(duì)用戶來(lái)說(shuō)，傳感器網(wǎng)絡(luò)的核心是感知的數(shù)據(jù)，而不是網(wǎng)絡(luò)硬件，如何對(duì)感知的數(shù)據(jù)進(jìn)行管理和處理成為決定傳感器網(wǎng)絡(luò)是否可用的關(guān)鍵[10]。近幾年來(lái)，研究人員嘗試將數(shù)據(jù)庫(kù)查詢語(yǔ)言應(yīng)用于傳感器網(wǎng)絡(luò)的數(shù)據(jù)密集型應(yīng)用。Fung W F等人提出，可以將整個(gè)網(wǎng)絡(luò)看成一個(gè)數(shù)據(jù)庫(kù)，通過(guò)聲明式查詢來(lái)實(shí)現(xiàn)對(duì)傳感器網(wǎng)絡(luò)的數(shù)據(jù)查詢[11]?？的螤柎髮W(xué)的Cougar系統(tǒng)[3]和加州大學(xué)伯克利分校的TinyDB系統(tǒng)[4]等均支持用SQL編寫的傳感器數(shù)據(jù)查詢，提供了節(jié)能的數(shù)據(jù)傳播和查詢的解決方案。在對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)設(shè)備容載的全局認(rèn)識(shí)基礎(chǔ)上，Strivastava U等人設(shè)計(jì)了有效的分布式查詢處理策略[12]。基于傳感器數(shù)據(jù)空間的和時(shí)態(tài)的特征，聲明式方法還被Jeffery S R等人運(yùn)用于清理網(wǎng)絡(luò)上的不安全數(shù)據(jù)[13]。

上述的傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢處理系統(tǒng)分為兩個(gè)層次，即運(yùn)行在查詢節(jié)點(diǎn)（如基站）上的DBMS層和運(yùn)行在智能終端設(shè)備上的DB層，如圖1所示。

查詢節(jié)點(diǎn)主要負(fù)責(zé)查詢的解析和優(yōu)化，生成分布式處理策略，并將查詢以“多跳”路由方式分發(fā)到傳感器節(jié)點(diǎn)上，傳感器節(jié)點(diǎn)上的數(shù)據(jù)查詢結(jié)果同樣以“多跳”路由方式返回到查詢節(jié)點(diǎn)。

傳感器智能終端的軟件構(gòu)建在微系統(tǒng)，如TinyOS[14]上，其面向設(shè)備的開(kāi)發(fā)模式需要用戶深入地了解設(shè)備的硬件配置、操作系統(tǒng)和技術(shù)標(biāo)準(zhǔn)，使用戶耗費(fèi)大量的時(shí)間和精力處理如存儲(chǔ)、并發(fā)以及通信協(xié)議等底層細(xì)節(jié)，是一件極其復(fù)雜的工作。對(duì)底層細(xì)節(jié)的定義給應(yīng)用的開(kāi)發(fā)與維護(hù)都帶來(lái)了很大困難，軟件模塊的復(fù)用性也很差，不能很好地滿足傳感器網(wǎng)絡(luò)快速部署所需的可擴(kuò)展性、易開(kāi)發(fā)性和易維護(hù)性等要求。

3 聲明式網(wǎng)絡(luò)開(kāi)發(fā)模式研究分析

在傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢處理系統(tǒng)處理數(shù)據(jù)查詢時(shí)，傳感器網(wǎng)絡(luò)分發(fā)查詢和收集結(jié)果的過(guò)程需要傳感器網(wǎng)絡(luò)根據(jù)路由策略建立路由，以保證節(jié)點(diǎn)的協(xié)同工作。因此，路由發(fā)現(xiàn)和維護(hù)是傳感器網(wǎng)絡(luò)處理數(shù)據(jù)查詢的基礎(chǔ)。傳感器網(wǎng)絡(luò)是無(wú)基礎(chǔ)設(shè)施、多跳結(jié)構(gòu)的，甚至是動(dòng)態(tài)的，其部署環(huán)境和條件差異性大，因此需要采用不同的路由策略，如生成樹(shù)、Ad Hoc網(wǎng)絡(luò)路由策略或者針對(duì)傳感器網(wǎng)絡(luò)特點(diǎn)設(shè)計(jì)的以數(shù)據(jù)為中心的、基于位置的、節(jié)能的路由策略[15～18]等。

面向系統(tǒng)的開(kāi)發(fā)模式同樣成為傳感器路由協(xié)議迅速部署的瓶頸。研究人員認(rèn)為，傳感器網(wǎng)絡(luò)的各種實(shí)現(xiàn)技術(shù)必須與傳感器網(wǎng)絡(luò)數(shù)據(jù)管理和處理技術(shù)密切結(jié)合，融為一體，而不是像目前其他網(wǎng)絡(luò)設(shè)計(jì)那樣分而為之，這樣才能夠設(shè)計(jì)實(shí)現(xiàn)高效率的以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)系統(tǒng)[10]。比如，可以將路由發(fā)現(xiàn)和維護(hù)也看作網(wǎng)絡(luò)數(shù)據(jù)查詢問(wèn)題，利用傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢技術(shù)來(lái)處理路由等網(wǎng)絡(luò)計(jì)算問(wèn)題。

3.1 聲明式網(wǎng)絡(luò)開(kāi)發(fā)模型分析比較

SQL語(yǔ)言是非遞歸語(yǔ)言，其本身不能定義如圖的連通性、可達(dá)性等問(wèn)題，并不適合定義網(wǎng)絡(luò)路由協(xié)議。而作為霍恩子句邏輯的不動(dòng)點(diǎn)擴(kuò)展，Datalog語(yǔ)言被用來(lái)描述包含遞歸運(yùn)算的數(shù)據(jù)計(jì)算功能[19]。因此，以遞歸的Datalog語(yǔ)言為基礎(chǔ)，Loo BT等人[7]以及Grumbach S等人[8]提出用遞歸的網(wǎng)絡(luò)查詢語(yǔ)言來(lái)描述網(wǎng)絡(luò)通信協(xié)議，稱之為“聲明式網(wǎng)絡(luò)”，定義如路由發(fā)現(xiàn)協(xié)議[20]、覆蓋網(wǎng)絡(luò)[21]、Ad Hoc網(wǎng)絡(luò)路由[22,23]等，而將底層物理細(xì)節(jié)的實(shí)現(xiàn)交予系統(tǒng)處理。類似的工作還包括提供異步系統(tǒng)診斷[24]、網(wǎng)絡(luò)監(jiān)控[25]、節(jié)點(diǎn)探索[26]、QoS 路徑維護(hù)[27]、拓?fù)涮剿鱗28]、網(wǎng)絡(luò)安全[29]等。這些工作提供了新的面向應(yīng)用的網(wǎng)絡(luò)開(kāi)發(fā)模式。

Loo BT等人提出的聲明式網(wǎng)絡(luò)開(kāi)發(fā)模型支持基于規(guī)則的遞歸的網(wǎng)絡(luò)查詢語(yǔ)言NDlog，建立在網(wǎng)絡(luò)節(jié)點(diǎn)配置的P2系統(tǒng)之上[7,30]，如圖2所示。P2系統(tǒng)執(zhí)行“半分布式”的程序，即程序定義的是涉及多個(gè)相互協(xié)同工作的節(jié)點(diǎn)的行為。P2系統(tǒng)是基于數(shù)據(jù)流的，系統(tǒng)生成程序的分布式執(zhí)行策略，從而將程序的執(zhí)行分布到所涉及的每一個(gè)節(jié)點(diǎn)上。NDlog語(yǔ)言具有地址指令，用以規(guī)定程序執(zhí)行所涉及的相關(guān)節(jié)點(diǎn)。如Navarro JA等人所述，NDlog語(yǔ)言缺乏形式化定義的語(yǔ)法和語(yǔ)義，語(yǔ)義的隨意性對(duì)研究和發(fā)展造成了一些困擾[31]。比如，其否定謂詞的語(yǔ)義規(guī)定十分模糊。另外,NDlog語(yǔ)言在表達(dá)能力方面有所局限，沒(méi)有適合描述網(wǎng)絡(luò)動(dòng)態(tài)性和實(shí)時(shí)性的原語(yǔ)，因此缺乏對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)性的有效支持。

Grumbach S等人提出的聲明式網(wǎng)絡(luò)開(kāi)發(fā)模型支持基于規(guī)則的遞歸的網(wǎng)絡(luò)查詢語(yǔ)言Netlog[8,32]，建立在網(wǎng)絡(luò)節(jié)點(diǎn)配置的 Netquest虛擬機(jī)之上[33～36]，如圖 3所示。Netquest虛擬機(jī)支持分布式程序，即程序只描述節(jié)點(diǎn)本地的功能。Netlog語(yǔ)言囊括了盡可能完備的網(wǎng)絡(luò)應(yīng)用所需要的原語(yǔ)，包括通信原語(yǔ)、聚合函數(shù)、時(shí)效聲明、間歇性觸發(fā)操作、非確定性選擇操作以及否定謂詞和刪除操作，具有豐富的表達(dá)能力，并具有形式化定義的語(yǔ)法和分布式不動(dòng)點(diǎn)語(yǔ)義[8,32]。Netlog程序是完全分布式的，節(jié)點(diǎn)不能讀或者寫其他節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)，這使得定義否定謂詞和刪除操作的語(yǔ)義變得簡(jiǎn)單，同時(shí)也使得Netlog語(yǔ)言符合網(wǎng)絡(luò)安全的需要。Netquest系統(tǒng)依賴于微型嵌入式 DBMS，如 SQLite、Solid DB、SQL Server Compact等，將Netlog規(guī)則編譯為SQL語(yǔ)句，再通過(guò)演繹引擎控制查詢語(yǔ)句的循環(huán)執(zhí)行。因?yàn)樵黾恿薉BMS這一層中間件，Netquest系統(tǒng)相對(duì)于P2系統(tǒng)而言，以執(zhí)行效率的代價(jià)換來(lái)了較高的可移植性。

與傳統(tǒng)的網(wǎng)絡(luò)編程方式相比，聲明式網(wǎng)絡(luò)開(kāi)發(fā)模型具有以下顯著的優(yōu)點(diǎn)：它具有非常簡(jiǎn)潔的程序（與命令式語(yǔ)言相比尺寸小一到兩個(gè)數(shù)量級(jí)）[34]；與底層實(shí)現(xiàn)無(wú)關(guān)，可以快速建立原型[33]；可以形式化地定義語(yǔ)言的語(yǔ)義[8,32]；程序的形式驗(yàn)證更加便利[37,38]。

3.2 聲明式網(wǎng)絡(luò)開(kāi)發(fā)模式研究建議

在以上工作中，用戶用聲明式語(yǔ)言描述的網(wǎng)絡(luò)算法是分布式的，節(jié)點(diǎn)利用分布式執(zhí)行策略[9]或本地查詢引擎[34]執(zhí)行分布式的聲明式程序，完成協(xié)同工作。而在傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢處理系統(tǒng)中，查詢的分布式處理過(guò)程對(duì)用戶是透明的，用戶將整個(gè)網(wǎng)絡(luò)看成一個(gè)數(shù)據(jù)庫(kù)，向其提出對(duì)全網(wǎng)感知數(shù)據(jù)的SQL查詢，并不需要考慮查詢是如何分布式地在各個(gè)節(jié)點(diǎn)上執(zhí)行的。同樣，對(duì)于路由查詢等網(wǎng)絡(luò)計(jì)算，仍希望能夠達(dá)到“用戶只需聲明網(wǎng)絡(luò)整體性質(zhì)，而將分布式計(jì)算交予網(wǎng)絡(luò)完成”的目標(biāo)，即全局式的網(wǎng)絡(luò)開(kāi)發(fā)模型。這樣，用戶只需提供對(duì)路由、生成樹(shù)等網(wǎng)絡(luò)功能的全局性描述，而將分布式執(zhí)行交給系統(tǒng)完成，即系統(tǒng)負(fù)責(zé)為用戶定義的全局式程序生成分布式執(zhí)行和優(yōu)化策略。通過(guò)這種模式，用戶可以在更高的抽象層次上進(jìn)行傳感器網(wǎng)絡(luò)的開(kāi)發(fā)。

1 Marron J,Minder D.Embedded WiSeNts research roadmap.Berlin:Logos Verlag Berlin,2006

2 Hejlsberg A.Trends and future directions in programming languages.http://channel9.msdn.com/Blogs/adebruyn/TechDays-2010-Developer-Keynote-by-Anders-Hejlsberg

3 Demers A J,Gehrke J,Rajaraman R,et al.The cougar project:a work-in-progress report.In:SIGMOD Record,2003

4 Madden S,Franklin M J,Hellerstein J M，et al.Tinydb:an acquisitional query processing system for sensor networks.ACM Transactions on Database Systems,2005,30(1)

5 Abiteboul S,Hull R,Vianu V.Foundations of databases.Addison-Wesley,1995

6 Ebbinghaus H D,Flum J.Finite model theory.Springer-Verlag,Berlin,1999

7 Loo B T,Condie T,Garofalakis M N,et al.Declarative networking:language,execution and optimization.ACM SIGMOD International Conference on Management of Data,Chicago,Illinois,USA,2006

8 Grumbach S, Wang F.Netlog,a rule-based language for distributed programming.Practical Aspects of Declarative Languages,12th International Symposium （PADL 2010）,Madrid,Spain,Springer,2010

9 Ramakrishnan R,Gehrke J.Database management systems.McGrawHill,2003

10 李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)與感知數(shù)據(jù)管理的概念、問(wèn)題與研究進(jìn)展.軟件學(xué)報(bào),2003，14（10）：1717～1727

11 Fung W F,Sun D,Gehrke J.Cougar:the network is the database.In:SIGMOD Conference,2002

12 Srivastava U,Munagala K,Widom J.Operator placement for innetwork stream query processing.Twenty-fourth ACM Symposium on Principles of Database Systems,2005

13 Jeffery S R,Alonso G,Franklin M J,et al.Declarative support for sensor data cleaning.In:Pervasive Computing,4th International Conference,2006

14 TinyOS.http://www.tinyos.net

15 Al-Karaki J M,Kamal A E.Routing techniques in wireless sensor networks:a survey.IEEE Personal Communications,2004

16 Chalermek I,Ramesh G,Deborah E.Directed diffusion:a scalable and robustcommunication paradigm for sensor networks.MobiCom,2000

17 Stojmenovic I.Position based routing in ad hoc networks.IEEE Communications Magazine,2002

18 Alexandru C,Mario A N,Jorg S.A framework for spatiotemporal query processing over wireless sensor networks.In:Proc of the 1st Int’l Workshop on Data Management for Sensor Network in Conjunction with VLDB,2004

19 Ramakrishnan R,Ullman J D.A survey of deductive database systems.Logic Programming,1995,23(2):125～149

20 Loo B T,Hellerstein J M,Stoica I,et al.Declarative routing:extensibleroutingwith declarativequeries.ACM SIGCOMM 2005 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications,Philadelphia,Pennsylvania,USA,2005

21 Loo B T,Condi T,Hellerstein J M,et al.Implementing declarative overlays.20th ACM Symposium on Operating Systems Principles,Brighton,UK,2005

22 Grumbach S,Lu J L,Qu WW.Self-organization of wireless networks through declarative local communication.In:OTM,On the Move Conference,MONET Workshop,2007

23 Perkins C E,Bhagwat P.Highly dynamic destination-sequenced distance-vector routing(DSDV)for mobile computers.In:ACM Conferenceon CommunicationsArchitectures,Protocolsand Applications,SIGCOMM'94,London,UK,1994

24 Abiteboul S,Abrams Z,Haar S,et al.Diagnosis of asynchronous discrete event systems:datalog to the rescue!In:Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,Baltimore,Maryland,USA,2005

25 Reiss F,Hellerstein J M.Declarative network monitoring with an underprovisioned query processor.ICDE,2006

26 Alonso G,Kranakis E,Sawchuk C,et al.Probabilistic protocols for node discovery in Ad Hoc multi-channel broadcast networks.Ad-Hoc,Mobile,and Wireless Networks,Second International Conference,ADHOC-NOW,2003

27 Bejerano Y,Breitbart Y,Orda Y,et al.Algorithms for computing QoS paths with restoration.IEEE/ACM Trans Netw,2005,13(3)

28 Bejerano Y,Breitbart Y,Garofalakis M N,et al.Physical topology discovery for large multi-subnet networks.INFOCOM,2003

29 Abadi M,Loo BThau.Towards a declarative language and system for secure networking.In:Proceedings of the 3rd USENIX International Workshop on Networking Meets Databases,Berkeley,CA,USA,2007

30 Attiya H,Welch J.Distributed computing :fundamentals,simulations and advanced topics.Wiley-Interscience,2004

31 Thomas C,Philippe P.Optimized link state routing protocol(OLSR).Network Working Group,2003

32 Grumbach S,WangF.Netlog,arule-based language for distributed programming.Manuscript for Journal of Theory and Practice of Logic Programming:Special Issue for 12th International Symposium of PADL.Cambridge University Press,2011

33 Bauderon M,Grumbach S,Gu D,et al.Programming iMote networks made easy.The Fourth International Conference on Sensor Technologies and Applications,SENSORCOMM 2010,Venice/Mestre,Italy,2010

34 Suo K,Qu W W,Iriondo AB.Declarative programming of network protocols.In:International Conference on Communication Technology,Nanjing,China,2010

35 Bauderon M,Bobineau C,Grumbach S,et al.Netquest:an abstract modelforpervasive applications.In:the 7th International Conference on Pervasive Computing,2009

36 Bellemon E,Dubosclard V,Grumbach S,et al.QuestMonitor:a visualization platform fordeclarative network protocols.MSV 2011:The 8th International Conference on Modeling,Simulation and Visualization Methods,Las Vegas,USA

37 Wang A,Basu P,Loo BT,et al.Declarative network verification.In:Proceedings of the 11th International Symposium on Practical Aspects of Declarative Languages,Springer-Verlag,2009

38 Deng Y X,Grumbach S,Monin J F.A framework for verifying data-centric protocols.In:The 31th IFIP International Conference on Formal Techniques for Networked and Distributed Systems,Reykjavik,Iceland,2011

39 Perkins C E,Royer E M.Ad-Hoc on-demand distance vector routing.IEEE Workshop on Mobile Computing Systems and Applications,Los Alamitos,CA,USA,1999

40 Liu C,Mao Y,Oprea M,et al.A declarative perspective on adaptive MANET routing.In:Proceedings of the ACM workshop on Programmable routers for extensible services of tomorrow,PRESTO’08.ACM,New York,NY,USA,2008

41 Navarro J A, Rybalchenko A.Operationalsemantics for declarative networking.In:Proceedings of the 11th international sysposium on practical aspects of declarative languages,Springer-Verlag,2009

42 Loo BT,Condie T,Garofalaks M,et al.Declarative networking.Communication of the ACM,2009,52(11):97～108