Pierre Fraigniaud

Ann‐node tree has to be explored bykmobile agents (robots), starting at its root. Every edge of the tree must be traversed by at least one robot, and exploration must be completed as fast as possible. Even when the tree is known in advance, scheduling optimal collective exploration turns out to be NP‐hard. We investigate the problem of how communication among robots influences the time for exploring unknown trees. To this end, we consider two scenarios. In the first scenario, robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. In the second scenario robots are oblivious of one another, and each of them knows only the part of the tree previously explored by itself. We show that this difference of communication capability significantly influences time of collective exploration. Under the first scenario, we construct an exploration algorithm whose running time for any tree is onlyO(k/ logk) larger than the optimal exploration time with full knowledge of the tree, while under the second scenario we prove that every algorithm works in timeΩ(k) larger than optimal, for some trees. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 166–177 2006

Several papers considered the problem of routing inad hocwireless networks using the positions of the mobile hosts. Perimeter routing1,2gives an algorithm that guarantees delivery of messages in such networks without the use of flooding of control packets. However, this protocol is likely to fail if the transmission ranges of the mobile hosts vary because of natural or man‐made obstacles. It may fail because either some connections are not considered, which effectively results in a disconnection of the network, or because some crossing connections are used, which could misdirect the message. In this paper, we describe a robust routing protocol, a variant of perimeter routing, which tolerates up to 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected ad hoc wireless network without the use of message flooding whenever the ratio of the maximum transmission range to the minimum transmission range is at most √2. Copyright © 2003 John Wiley & Sons, Ltd.