声明式的传感器网络开发模式研究进展分析

汪 芳,张云勇,房秉毅

（中国联通集团研究院 北京 100048）

1 引言

近年来，随着无线通信技术和传感器终端设备的发展，传感器网络得到了较为广泛的应用。然而，设备的多样性和不稳定性、网络的动态性以及数据的密集性等特点给传感器网络的开发带来了各种挑战，尤其是针对传感器网络的数据查询和网络协议的开发。

传感器网络开发的一个瓶颈是缺乏编程抽象，这引起学术界和工业界的广泛重视。欧盟“传感器网络开发和控制协同嵌入式系统”项目（Embedded WiSeNts）研究路线图报告指出：“现在亟需一种新的高层编程模型，使抽象的层次从以系统为中心的编程提升到以应用为中心的编程。用户应该指定预期的行为，而不是必须去处理系统的细节。特别地，此类模型应支持通过对需要实现的功能的声明式描述来对传感器网络的整体进行编程，而不是针对单个节点的行为进行描述[1]，从而使用户从底层的细节中脱离出来，将注意力集中在高层的应用逻辑上”。

在计算机技术领域，声明式编程语言被认为是编程语言的未来发展趋势，以提供更高层抽象的编程模型[2]。数据查询语言，如SQL就是一种声明式的编程语言。近年来，研究人员尝试利用数据库管理系统（DBMS）对传感器网络数据进行管理和查询，以简化传感器数据密集型应用的开发[3,4]。此外，递归的Datalog语言可以描述图的连通性、可达性，如生成树和传递闭包等经典的图论问题[5,6]。因此，研究人员尝试利用Datalog语言的扩展来描述生成树和路由等网络计算问题，以提供声明式的网络开发模式[7,8]。本文介绍和分析声明式传感器网络开发模式的发展和现状，并提出未来研究发展的一些建议。

2 传感器网络声明式数据查询处理系统

回顾数据库领域的发展，逻辑层相对物理层的独立是数据库管理系统的基本原则。利用关系演算提供以数据为中心的应用的抽象模型带来关系数据库管理系统（RDBMS）在技术和商业上的巨大成功[9]。数据查询语言SQL为数据查询提供了声明式的方法，使数据的查询独立于数据的物理表示，而让数据库管理系统负责优化和执行。

传感器网络通过传感器节点的协同工作，对地理范围内的对象进行感知，采集并处理数据，并将处理结果发布给用户。对用户来说，传感器网络的核心是感知的数据，而不是网络硬件，如何对感知的数据进行管理和处理成为决定传感器网络是否可用的关键[10]。近几年来，研究人员尝试将数据库查询语言应用于传感器网络的数据密集型应用。Fung W F等人提出，可以将整个网络看成一个数据库，通过声明式查询来实现对传感器网络的数据查询[11]。康奈尔大学的Cougar系统[3]和加州大学伯克利分校的TinyDB系统[4]等均支持用SQL编写的传感器数据查询，提供了节能的数据传播和查询的解决方案。在对网络拓扑结构和节点设备容载的全局认识基础上，Strivastava U等人设计了有效的分布式查询处理策略[12]。基于传感器数据空间的和时态的特征，声明式方法还被Jeffery S R等人运用于清理网络上的不安全数据[13]。

上述的传感器网络数据查询处理系统分为两个层次，即运行在查询节点（如基站）上的DBMS层和运行在智能终端设备上的DB层，如图1所示。

查询节点主要负责查询的解析和优化，生成分布式处理策略，并将查询以“多跳”路由方式分发到传感器节点上，传感器节点上的数据查询结果同样以“多跳”路由方式返回到查询节点。

传感器智能终端的软件构建在微系统，如TinyOS[14]上，其面向设备的开发模式需要用户深入地了解设备的硬件配置、操作系统和技术标准，使用户耗费大量的时间和精力处理如存储、并发以及通信协议等底层细节，是一件极其复杂的工作。对底层细节的定义给应用的开发与维护都带来了很大困难，软件模块的复用性也很差，不能很好地满足传感器网络快速部署所需的可扩展性、易开发性和易维护性等要求。

3 声明式网络开发模式研究分析

在传感器网络数据查询处理系统处理数据查询时，传感器网络分发查询和收集结果的过程需要传感器网络根据路由策略建立路由，以保证节点的协同工作。因此，路由发现和维护是传感器网络处理数据查询的基础。传感器网络是无基础设施、多跳结构的，甚至是动态的，其部署环境和条件差异性大，因此需要采用不同的路由策略，如生成树、Ad Hoc网络路由策略或者针对传感器网络特点设计的以数据为中心的、基于位置的、节能的路由策略[15～18]等。

面向系统的开发模式同样成为传感器路由协议迅速部署的瓶颈。研究人员认为，传感器网络的各种实现技术必须与传感器网络数据管理和处理技术密切结合，融为一体，而不是像目前其他网络设计那样分而为之，这样才能够设计实现高效率的以数据为中心的传感器网络系统[10]。比如，可以将路由发现和维护也看作网络数据查询问题，利用传感器网络数据查询技术来处理路由等网络计算问题。

3.1 声明式网络开发模型分析比较

SQL语言是非递归语言，其本身不能定义如图的连通性、可达性等问题，并不适合定义网络路由协议。而作为霍恩子句逻辑的不动点扩展，Datalog语言被用来描述包含递归运算的数据计算功能[19]。因此，以递归的Datalog语言为基础，Loo BT等人[7]以及Grumbach S等人[8]提出用递归的网络查询语言来描述网络通信协议，称之为“声明式网络”，定义如路由发现协议[20]、覆盖网络[21]、Ad Hoc网络路由[22,23]等，而将底层物理细节的实现交予系统处理。类似的工作还包括提供异步系统诊断[24]、网络监控[25]、节点探索[26]、QoS 路径维护[27]、拓扑探索[28]、网络安全[29]等。这些工作提供了新的面向应用的网络开发模式。

Loo BT等人提出的声明式网络开发模型支持基于规则的递归的网络查询语言NDlog，建立在网络节点配置的P2系统之上[7,30]，如图2所示。P2系统执行“半分布式”的程序，即程序定义的是涉及多个相互协同工作的节点的行为。P2系统是基于数据流的，系统生成程序的分布式执行策略，从而将程序的执行分布到所涉及的每一个节点上。NDlog语言具有地址指令，用以规定程序执行所涉及的相关节点。如Navarro JA等人所述，NDlog语言缺乏形式化定义的语法和语义，语义的随意性对研究和发展造成了一些困扰[31]。比如，其否定谓词的语义规定十分模糊。另外,NDlog语言在表达能力方面有所局限，没有适合描述网络动态性和实时性的原语，因此缺乏对网络的动态性的有效支持。

Grumbach S等人提出的声明式网络开发模型支持基于规则的递归的网络查询语言Netlog[8,32]，建立在网络节点配置的 Netquest虚拟机之上[33～36]，如图 3所示。Netquest虚拟机支持分布式程序，即程序只描述节点本地的功能。Netlog语言囊括了尽可能完备的网络应用所需要的原语，包括通信原语、聚合函数、时效声明、间歇性触发操作、非确定性选择操作以及否定谓词和删除操作，具有丰富的表达能力，并具有形式化定义的语法和分布式不动点语义[8,32]。Netlog程序是完全分布式的，节点不能读或者写其他节点存储的数据，这使得定义否定谓词和删除操作的语义变得简单，同时也使得Netlog语言符合网络安全的需要。Netquest系统依赖于微型嵌入式 DBMS，如 SQLite、Solid DB、SQL Server Compact等，将Netlog规则编译为SQL语句，再通过演绎引擎控制查询语句的循环执行。因为增加了DBMS这一层中间件，Netquest系统相对于P2系统而言，以执行效率的代价换来了较高的可移植性。

与传统的网络编程方式相比，声明式网络开发模型具有以下显著的优点：它具有非常简洁的程序（与命令式语言相比尺寸小一到两个数量级）[34]；与底层实现无关，可以快速建立原型[33]；可以形式化地定义语言的语义[8,32]；程序的形式验证更加便利[37,38]。

3.2 声明式网络开发模式研究建议

在以上工作中，用户用声明式语言描述的网络算法是分布式的，节点利用分布式执行策略[9]或本地查询引擎[34]执行分布式的声明式程序，完成协同工作。而在传感器网络数据查询处理系统中，查询的分布式处理过程对用户是透明的，用户将整个网络看成一个数据库，向其提出对全网感知数据的SQL查询，并不需要考虑查询是如何分布式地在各个节点上执行的。同样，对于路由查询等网络计算，仍希望能够达到“用户只需声明网络整体性质，而将分布式计算交予网络完成”的目标，即全局式的网络开发模型。这样，用户只需提供对路由、生成树等网络功能的全局性描述，而将分布式执行交给系统完成，即系统负责为用户定义的全局式程序生成分布式执行和优化策略。通过这种模式，用户可以在更高的抽象层次上进行传感器网络的开发。

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 李建中，李金宝，石胜飞.传感器网络与感知数据管理的概念、问题与研究进展.软件学报,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