http://www.paper.edu.cn 无线传感网中的地域群播∗ 樊秀梅 E-mail：xmfan@bit.edu.cn 北京理工大学计算机科学技术学院，北京（100081） 摘 要：无线传感网与 Ad-hoc 网中的地域群播（Geocasting）意味着从源点传递消息到一给 定地理区域内的所有节点。地域群播可形成区域广播来传送和地理位置相关的商业信息、广 广告等，或发送紧急消息到指定区域等实际应用。设计地域群播协议的目标是保证消息传递 和低传输代价。大多数已提出的协议不保证消息传递，另一些协议虽保证消息传递却引发高 传输代价。现在的目标是研究保证消息传递和低传输代价的地域通信协议及其算法，推进地 域通信的发展。本文介绍了相关研究背景与已有研究成果，并提出存在的问题和解决思路。 关键词：地域群播，地域组播，路由，无线传感网，移动 Ad-hoc 网络 1. 前言 无线传感网络被美国商业周刊和 MIT 技术评论列为 21 世纪最有影响的 21 项技术和改 变世界 10 大技术之一，是未来网络的重要组成部分。它可用来进行环境监控、事件跟踪、 安全及系统控制等，也可认为是一个分布式数据库系统，支持不同类型的查询。其中一类称 为基于地域的查询要求在一个地理区域内的所有传感器参与，利于构建一个查询响应。例如 查询随后两小时内在一特定区域内所有交通工具的位置。为了支持这样的查询，监控中心（接 收器）应将这样的查询消息传递到查询地域的所有传感器。源节点发送一个消息到给定地理 区域内所有节点的方式被称为地域群播（Geocasting）[1]。在传感器网络和 Ad hoc 网络中， 地域群播是许多网络应用中的基本服务。 地域群播有许多有趣的应用。它可形成区域广播来传送和地理位置相关的商业信息、广 告等，诸如为到达某一地理区域的交通工具发送该范围内的停车场位置和空闲车位等信息。 另外发送紧急消息到指定区域也是其一个重要应用。 地域群播算法的目标包括两部分：保证消息传递和低传输代价。保证消息传递确保在查 询地域内每个传感器可以收到地域群播消息的副本；低传输代价可以尽可能地节约能量，适 应能量有限且多数情况下无法更换电池的传感器需求。为了实现地域群播，许多算法[1-10]已 经被研究者们提出。但提出的一些方法[2-9]不保证消息的传递，并引起较高的传输代价。文 献[1]和[10]中提出的四个算法可以保证消息传递，但传输代价较高。在所有提出的地域群播 算法中，分割面穿越的限定性洪泛法 RFIFT（Restricted Flooding with Intersected Face Traversal) [1]是最有效的一种。 2. 国内外研究现状及分析 （1）研究背景与历史 地域群播概念在 1997 年第一次被 Navas 和 Imielinski[12]提出，其根本问题就是将一个消 息从源点发送到一定地理区域内（例如一幢建筑，一条街道，一个校园，一个商业区域，旅 游胜地等等）的所有节点，也称为基于位置的广播[13]。因为许多应用的通信目标是到达一 定区域内的所有节点，故地域群播是 Ad hoc 网络和无线传感网中一个重要的通信手段，例 ∗本课题得到国家自然科学基金（No. 90604012）和北京理工大学基础研究基金（No. BIT-UBF-200501F4209） 的资助。 -1- 

http://www.paper.edu.cn 如联系监控区域的所有有效传感器去定期收集数据，或为了报告方便将它的位置通知覆盖一 定区域的传感器。 在 MANET 中的第一个 Geocasting 工作在文献[2]中提出，其主要思想是基于限制的洪 泛转发。源主机和目的域的位置信息决定了转发的洪泛区域。通常转发区域被定义为包括发 送者和目的域位置的最小长方形。在转发区域的节点收到 Geocast 消息时将重新广播这个消 息，而不在转发区域的节点收到 Geocast 消息时将丢弃这个消息。但这种方式仍然存在着转 发区域内的不必要洪泛分组。 许多地域群播协议已经提出[3-9,13,14]，但不能保证递送到地域群播区域 R 内的所有节点。 散布在地理区域内的传感器可能由于区域内的障碍或通信和感知半径的差异导致它们并不 能相互连接。一种“‘forgotten’ face tree traversal scheme）”[11,15]可以保证信息的传递，但具 有相当大的信息开销。 （2）已提出的地域群播路由协议分类 对已经提出的地域群播路由协议，文献[16]将其分为三大类： a. 基于洪泛的协议（flooding-based protocols）：使用洪泛或洪泛变化将地域群播分组 从源点转发到地域群播区域，限定性洪泛转发区域是包括源点和地域群播区域的最小矩形。 这 类 协 议 包 括 Location-Based Multicast (LBM)[2] 、 Voronoi diagram based geocasting protocol[5]、Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks[6]。这些协议即 使减小了洪泛区域，但仍然引起较高的洪泛代价，同时并不保证消息传递[1]。 b. 基于路由的协议（routing-based protocols）：通过控制分组产生从源到地域群播区域 的路由。这类协议包括 Mesh-based Geocast Routing Protocol (MGRP) [17], Geocast Adaptive Mesh Environment for Routing (GAMER)[9] and GeoTORA [18]。Seada 等人[20]提出一个将地理 路由机制和区域洪泛综合起来实现高传递率和低开销的有效实用地域群播协议。尽管这些协 议减小了消息的传输数量，但并不确保消息的传递[1]。 c. 基于簇的协议（cluster-based protocols）：根据地理信息将 MANET 分割成几个不连 接的、相等大小的蜂窝区域，并在每个区域选择一个簇头来执行信息交换。这类协议包括 GeoGRID [13], Obstacle-Free Single-Destination Geocasting Protocol (OFSGP) and Obstacle-Free Multi-Destination Geocasting Protocol (OFMGP) [19]。这些协议尽管提高了消息的传递率，但 也引起较大的传输代价[1]。 （3）地域群播综合方法 为了克服上述地域群播协议和算法的不足，近年来一些将基于位置单播、限定性洪泛和 面穿越（face traversal）方式综合在一起的算法已被提出来保证消息的传递[1,10,11]。深度优先 面树穿越法（DFFTT）[11]首先使用 GFG（Greedy-Face-Greedy）将地域群播消息传递到 R 内 的一个节点，然后一个覆盖和地域群播域 R 相交所有面的面树（face tree）被构建，最后通 过面树上的每个节点，消息就被传递到 R 中的所有节点；RFIFT[10] 首先使用 GFG 将地域群 播消息通过基于位置的单播路由方式传递到 R 内的一个节点，然后在 R 内形成限定性洪泛 去穿越和 R 相交的所有面；基于组播的入口带（entrance zone）地域群播法（EZMG）[1]将 地域群播域 R 的环绕区域划分成一系列入口带，源点发送消息时就组播到所有入口带，入 口带收到消息的节点就广播这个消息，然后 R 内的所有节点都听到了这个消息。这些方法 保证了信息的传递，但也引起较大的传输代价。 （4）地域组播技术 MANET 中的地域组播（Geomulticasting）是一个没有被太多研究的领域。地域组播[8] -2- 

http://www.paper.edu.cn 是在一个特定区域中将消息传递到一些特殊用户组的技术，是一种特殊的依赖于位置的组播 技术，它定义地域组播组为一特定区域内一些特殊组的节点集合。[8]提出在移动 Ad-hoc 无 线网络等限定性环境中支持地域组播服务的体系结构和协议，它们具有代价有效性和消息传 递的高精确性。[8]采用聚类技术将不同移动节点形成一个簇（cluster）。为了节约资源和减 小能耗，在每个簇里选举一个簇头（clusterhead）作为地域组播中的组成员节点。当收到组 播信息后，簇头在自己的簇里进行广播。已有几种聚类算法来决定簇头。一种是最小 ID 算 法[21]，另一种是最高连接（度）算法[22]，还有一种是基于移动的聚类算法（MBC）[8]； [23]提出一种移动自适应聚类方式，它通过主动单播路由算法刻划了网络链路将来可用的概 率模型。 3. 存在问题和解决问题的新思路 现在国际研究界已有关于地域通信方面的一些研究成果，包括地域群播和地域组播等形 式，但都不是很完善，还存在着一些问题。我们认为最关键的问题及其解决思路有如下几点： （1） 现有的地域群播协议与算法不能同时满足保证消息传递和低传输代价这两个基本 目标。保证消息传递和低传输代价是地域群播设计中的两个基本目标，也是相互矛盾、制约 的两个因素。现有的地域群播协议不能同时满足这两个基本要求，设计兼顾保证消息传递和 低传输代价的地域群播协议将是解决的关键问题和难点问题。 （2） 现有的地域群播协议与算法没有很好考虑节点的移动性。这和实际状况不大符合。 为此需要在考虑节点移动状况下的地域群播协议与算法。 （3） 当几个处于不同位置的地理区域需传递同一消息时，没有有效解决机制。进一步 的研究需要考虑在节点移动状态下，不同地理区域间的组播通信问题。我们提出准动态建立 和维护移动环境中的组播树、按需计算组播树等理念，设计自适应、低开销的地理组播协议 与算法，以适应不同地理区域间的消息传递。 （4） 在现有地域群播协议中没有一个确认机制来提高传输的可靠性。进一步的研究目 标将是研究一种地理广播的可靠传输协议，在不降低资源利用率的情况下，提高消息传递的 可靠性。 （5） 地域群播和地域组播的应用还具有较大的局限性。现有地理广播与地理组播的应 用还仅局限在监控、紧急信息发布等应用，下一步的研究内容将是根据应用需求开发不同环 境、不同行业的各种适用背景与应用场所。 4. 结语 本文针对现在已经提出的地域群播和地域组播等协议和算法做了一个分析和介绍，并提 出了现有成果中存在的问题和进一步的解决思路。希望能够抛砖引玉，让更多的研究者加入 这一研究领域，共同推进无线传感网与移动 Ad-hoc 网络中的地域群播和地域组播研究，并 尽快将其应用与实际环境中，加快我国无线网络的发展，提升国际竞争力。 -3- 

参考文献 http://www.paper.edu.cn [1] Stojmenovic, “Geocasting with Guaranteed Delivery in Sensor Networks,” IEEE Wireless Communications, vol.11(6),2004, pp.29–37. [2] Y. B. Ko and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks:Location-Based Multicast Algorithms,” in Proc. of Workshop on Mobile Computer System and Applications, pp. 101–110，1999. [3] S. Basagni, I. Chlamtac, and V. R. Syrotiuk, “Geographic Messaging in Wireless Ad Hoc Networks,” in Proc. of VTC, Houston, TX, pp 1957-1961, May 1999. [4] S. Kwon and N. B. Shroff, "Geographic Routing in the Presence of Location Errors," in Proc. Int’l Conf. Broadband Networks, pp. 622-630，Oct.2005. [5] Stojmenovic, A. P. Ruhil, and D. K. Lobiyal, “Voronoi Diagram and Convex Hull-Based Geocasting and Routing in Wireless Networks,” in Proc. IEEE Symposium on Computer and Communication, Kemer-Antalya, Turkey, pp.51-56, June 2003. [6] Y. B. Ko and N. H. Vaidya, “Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks,” Mobile Networks and Applications, vol. 7, no. 6, pp. 471-480, 2002. [7] C. Schwingenschlogl and T. Kosch, “Geocast Enhancements of AODV for Vehicular Networks,” ACM Mobile Computing and Communication, vol. 6, no. 3, pp. 96–97, 2002. [8] B. An and S. Papavassiliou, “Geomulticasting: Architectures and Protocols for Mobile Ad Hoc Networks,” Journal of Parallel and Distributed Computing, vol.63, pp.182–195, 2003. [9] T. Camp and Y. Liu, “An Adaptive Mesh-Based Protocol for Geocast Routing,” Journal of Parallel and [10] K. Seada and A. Helmy, “Efficient Geocasting with Perfect Delivery in Wireless Networks,” in Proc. Distributed Computing, vol. 63, pp. 196–213, 2003. Wireless Communications and Networking, 2004. [11] P. Bose, P. Morin, I. Stojmenović, and J. Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, vol.7, no.6, pp.609-616, 2001. [12] J. C. Navas and T. Imielinski, Geographic Addressing and Routing, In Prof.of the Third ACM MOBICOM ,Budapest, Hungary, 26-30,Sep.1997. [13] W.H. Liao, Y.C. Tseng, K.L. Lo, J.P. Sheu, GeoGRID: A geocasting protocol for mobile ad hoc networks based on grid, Journal of Internet Technology, 1, pp.23-32, 2000. [14] Q. Huang, C. Lu, G.C. Roman, Mobicast: Just-in-time multicast for sensor networks under spatiotemporal constraints, TR WUCS-02-42, Washington Univ., St. Louis, USA, Dec. 2002. [15] P. Morin, Online routing in geometric graphs, PhD thesis, School of Computer Science, Carleton University, January 2001. [16] P.Yao, E.Krohne, and T.Camp，Performance Comparison of Geocast Routing Protocols for a MANET， Technical report, Department of Math. and Computer Sciences,Colorado School of Mines, May 2004. [17] J. Boleng, T. Camp, and V. Tolety. Mesh-based geocast routing protocols in an ad hoc network. In [18] Y. Ko and N. H. Vaidya. GeoTORA: A protocol for geocasting in mobile ad hoc networks. In Proceedings Proceedings of IPDPS, pages 184.193, April 2001. of ICNP, pages 240.250, November 2000. [19] C.-Y. Chang, C.-T. Chang, and S.-C. Tu. Obstaclefree geocasting protocols for single/multi-destination short message services in ad hoc networks. Wireless Networks, 9(2):143.155, 2003. [20] K.Seada, A.Helmy, and R.Govindan, On the Effect of Localization Errors on Geographic Face Routing in Sensor Networks, IEEE/ACM 3rd International Symposium on Information Processing in Sensor Networks (IPSN), Berkeley, CA, April 2004. [21] Ephremides, J.E. Wieselthier, D.J. Baker, A design concept for reliable mobile radio networks with frequency hopping signaling, Proceedings of IEEE 75 (1) (1987) 56–73. [22] M. Gerla, J.T. Tsai, Multicluster, mobile, multimedia, radio network, ACM/Baltzer J. Wireless Networks J. 1 (3) (1995)，255–265. [23] T. Imielinski and J. Navas, GPS-based Addressing and Routing, IETF RFC 2009, November (1996) [24] J. Lian, S. Naik, Y. Liu, and L. Chen, “Virtual Surrounding Face Based Geocasting with Guaranteed Message Delivery for Ad Hoc and Sensor Networks”, in Proc. IEEE ICNP, Nov, 2006. [25] E. Kranakis, H. Singh, and J. Urrutia, “Compass Routing on Geometric Networks,” In Proc. Canadian Conference on Computational Geometry, 1999, pp. 51-54. -4- 

http://www.paper.edu.cn Geocasting Research in Wireless Sensor Networks School of computer science and technology, Beijing Institute of Technology, Beijing（100081） Fan Xiumei Abstract Geocasting in Wireless Sensor Networks and Mobile Ad-hoc Networks means to send a message to all the nodes in a given geographic area. Geocasting can form area broadcast to transfer commerce information and advertisements based on geography position. An important objective of a geocasting algorithm is to achieve guaranteed message delivery while maintaining a low cost. Of the existing approaches, some approaches presented do not guarantee message delivery and incur high transmission costs. The others guarantee message delivery in continuous geocasting regions. but these algorithms have high transmission costs. The current object is to research geocasting that guarantee message delivery and low cost so that to advance the development of geography area communication. In this paper, we introduce related geocasting research background and some foregone algorithms. At the same time ,we propose some existent problem and solving ideas. Keywords: Geocasting; Geomulticasting; Routing; Wireless Sensor Networks; Mobile Ad-hoc Networks 作者简介：樊秀梅，博士，副教授；研究领域为计算机网络传输控制、QoS、无线网络、网 络性能评价。 -5-