Command Channel Management

Even with an arbitrarily large number of robots sharing a single broadcast channel, it is possible for the user to initiate a one-to-one session with one of a situationally addressed group of nodes, no matter what their number, and the same process will tell the user approximately how many members actually are in the group. The key is to understand and exploit the statistics of a contention communication channel, and to command the nodes to transmit a message with a probability chosen so that one of the messages will get through in short order, where the definition of "short order" will depend on the characteristics of the command channel's physical layer.

For example, on a carrier-sense multiple access (CSMA) channel like Ethernet, a node desiring to transmit a message can defer its own transmission when it detects another transmitter's signal carrier on the channel. Collision-detection (CD -- another Ethernet property) permits a transmitting node to immediately determine if its own transmission is colliding with that of another node, and it is therefore able to "jam" the channel to guarantee that all transmitting nodes detect the collision and then "backoff" according to some prescribed algorithm before transmitting again. Since CSMA and CD capabilities can only help make channel utilization more efficient, let us consider the worst possible case of a pure contention channel, in which each node must transmit "blind". This is the case, for example, in a satellite channel, and the analyses of the pure Aloha and slotted Aloha access techniques developed for satellites in the early 1970s apply [TAN81].

At any point in time, the number of nodes transmitting is either 0, 1, or greater than 1. If exactly one node transmits for the entire duration of its message, then the message is received by the other nodes; if more than one node transmits during any portion of a message, then the messages "collide" and are not received. If nodes are permitted to start to transmit whenever they desire (pure Aloha), then a maximum throughput efficiency of about 18% is achievable when the offered load (number of nodes times probability of each node transmitting at any point in time) is equal to 0.5. If the nodes are constrained to start their message transmissions at specific points in time (i.e., time is divided into slots), then the maximum efficiency is about 36%, occuring when the offered load is 1.0.

So the master simply makes an estimate E of the number of nodes in the group, and commands them all to transmit, with probability p = 1/E, a brief message into each of a specified small number of slots (2-10). If E is significantly greater than the actual number of nodes N, then the actual offered load will be too low and the slots will all be empty. If E is too small, then all the slots will see collisions (see Figure 1 below). In either case, no messages will be received by anyone. If the master node is able to distinguish between an emply slot and a collision (it doesn't matter if the slave nodes can do so), then it is possible to perform a binary search in log E. If empty slots and collisions look the same to the master (which is entirely likely with a covert channel), then the master must scan the entire range of possible N until he receives a message -- a simple geometric scan of E with the value of E changing by a factor of 2 for each successive slot has a probability of approximately .81 of yielding at least one successful message. Providing two slots for each value of E thus will yield better than .96, and three slots achieves .993.

In either case, once E is close to N, additional probes using larger numbers of slots can determine N to whatever precision is desired, and the master can send messages to the individual unique addresses returned in the successful response messages.

Figure 1. Probabilities of successful message transmission, collisions, and empty slots for Slotted Aloha channel access, plotted as a function of the logarithm of the ratio of estimated number of nodes to actual number. Log (E/N) = 0 corresponds to an offered load of 1.0. Empty slots occur to the right of the peak, collisions to the left.

Modulated Retroreflector

The systems of "gnat" sized and (potentially much) smaller robots that MEMS technology may ultimately make feasible will involve additional communications difficulties. Severe power limitations will probably preclude the use of actively powered transmitters over any significant distance, including the display of lights proposed below. One option (which has been proposed several times in the past, at least as early as 1977) is to incorporate a modulated retroreflector into the "slave" units. The active node (master) illuminates the passive nodes with a laser beam, and the passive nodes modulate the signal which is retroreflected back to the active node. The carrier beam can be directly modulated for half-duplex operation, or two modulated subcarriers can be employed to provide full-duplex communications. This scheme allows the active node (the master) to provide all the power for communications in both directions. In addition, the passive nodes do not require a precise pointing system to achieve this high signal gain. The development of a "standard cell" MEMS modulated retroreflector would be a valuable addition to the microrobot toolbox. Pister and his students at UCLA have explored the fabrication of such devices. [GUN95]

Up to Many Robot Systems

Robotics home page

Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 1 December 1998.