A hierarchical approach to position-based multicast for mobile ad-hoc networks

In this paper we present Scalable Position-Based Multicast (SPBM), a multicast routing protocol for ad-hoc networks. SPBM uses the geographic position of nodes to provide a highly scalable group membership scheme and to forward data packets in a way that is very robust to changes in the topology of the network. SPBM bases the forwarding decision on whether or not there are group members located in a given direction, allowing a hierarchical aggregation of membership information. The farther away a region is from an intermediate node, the higher the level of aggregation for this region should be. Because of aggregation, the overhead for group membership management scales logarithmically with the number of nodes and is independent of the number of multicast senders for a given multicast group. Furthermore, we show that group management overhead is bounded by a constant if the frequency of membership updates is scaled down with the aggregation level. This scaling of the update frequency is reasonable since the higher the level of aggregation is, the lower the number of membership changes for the aggregate will be. The performance of SPBM is investigated by means of simulation, including a comparison with ODMRP, and through mathematical analysis. We also describe an open source kernel implementation of SPBM that has been successfully deployed on hand-held computers.