MFACE: A Multicast Backbone-Assisted Face Traversal Algorithm for Arbitrary Planar Ad Hoc and Sensor Network Topologies

Face is a well-known localized routing protocol for ad hoc and sensor networks which guarantees delivery of the message as long as a path exists between the source and the destination. This is achieved by employing a left/right hand rule to route the message along the faces of a planar topology. Although face was developed for the unicast case, it has recently been used in combination with multicasting protocols, where there are multiple destinations. Some of the proposed solutions handle each destination separately and lead thus to increased energy consumption. Extensions of face recovery to the multicast case described so far are either limited to certain planar graphs or do not provide delivery guarantees. A recently described scheme employs multicast face recovery based on a so called multicast backbone. A multicast backbone is a Euclidean spanning tree which contains at least the source and the destination nodes. The idea of backbone assisted routing it to follow the edges of the backbone in order to deliver a multicast message to all spanned destination nodes. The existing backbone face routing scheme is however limited to a certain planar graph type and a certain backbone construction. One of the key aspects of the multicast face algorithm MFACE we propose in this work is that it may be applied on top of any planar topology. Moreover, our solution may be used as a generic framework since it is able to work with any arbitrary multicast backbone. In MFACE, any edge of the backbone originated at the source node will generate a new copy of the message which will be routed toward the set of destination nodes spanned by the corresponding edge. Whenever the message arrives at a face edge intersected by a backbone edge different from the initial edge, the message is split into two copies, both handling a disjoint subset of the multicast destinations which are defined by splitting the multicast backbone at that intersection point.