Proposed by David A. Burke, Kenneth N. Brown

This benchmark specification originates from the Centre for Telecommunications Value-chain Research and Cork Constraint Computation Centre, Dept. of Computer Science, University College Cork, Ireland. This work is supported by Science Foundation Ireland under Grant No. 03/CE3/I405.

An ad hoc network is a collection of wireless devices that form a network without any centralised infrastructure. When the devices are deployed they must first configure themselves to form a correctly functioning network. One configuration task when operating in a battery limited environment is the Minimum Energy Broadcast (MEB) problem. Assume a network of devices with omnidirectional antennas. The aim is to configure the power level in each device such that if a specified source device broadcasts a message it will reach every other device either directly or by being retransmitted by an intermediate device (a broadcast tree is formed). The desired configuration is that which minimises the total energy required by all devices, thus increasing the lifetime of the network.

Several approaches (both centralised and distributed) have been proposed for solving this problem. See the references page of this benchmark for more information. As there is no central controller and in a large network centralising the entire problem may be infeasible, Distributed Constraint Optimisation (DisCOP) is one appropriate way to model and solve the problem, and it is this approach that will be described in this specification.

To formulate the problem as a Distributed COP, we have an agent, *a _{i}*, representing each device in the network. The neighbours of

**Relationship variables:** For each neighbour *a _{j}*,

- 0 = the devices are not connected in the broadcast tree
- 1 =
*a*is the parent of_{i}*a*in the broadcast tree_{j} - 2 =
*a*is the child of_{i}*a*in the broadcast tree_{j}

An inter-agent constraint between each pair of neighbours ensures that the corresponding variables in neighbouring nodes match up correctly, i.e. both are 0, or else one is 1 and the other is 2. To construct a tree, each agent is constrained to have exactly one parent, except the source device, which is not allowed any parents.

**Power/energy variables:** The agents also have a private variable corresponding to each of these public variables set to be the energy cost incurred due to the setting of that public variable, i.e. if the public variable is 1 then the private variable is assigned the energy cost for broadcasting to that neighbour, otherwise it is assigned 0. A private constraint over all of these ‘energy cost’ variables states the total cost for *a _{i}* to broadcast to all of its children is the

**Hop-count variable:** Each agent also has a hop-count variable, indicating how many hops that device is from the source device. A second inter-agent constraint between neighbouring agents ensures that the hop-count of a child in the broadcast tree is one greater than its parent, thus preventing cycles.

Figure 1 displays an example MEB problem with 10 devices. This problem is modelled using the variables as specified in Table 1 and constraints as described in the previous paragraph. Its corresponding minimal energy broadcast tree is shown in Figure 2, and the optimal assignments to variables is shown in Table 2.

Variable | a1_{h} |
a1_{r}-3 |
a1_{p}-3 |
a1_{r}-4 |
a1_{p}-4 |
a1_{r}-7 |
a1_{p}-7 |
a1_{r}-8 |
a1_{p}-8 |
||||

Domain | 0-9 | 0,1,2 | 0,93 | 0,1,2 | 0,21 | 0,1,2 | 0,48 | 0,1,2 | 0,17 | ||||

Variable | a2_{h} |
a2_{r}-3 |
a2_{p}-3 |
a2_{r}-6 |
a2_{p}-6 |
a2_{r}-8 |
a2_{p}-8 |
a2_{r}-9 |
a2_{p}-9 |
a2_{r}-10 |
a2_{p}-10 |
||

Domain | 0-9 | 0,1,2 | 0,33 | 0,1,2 | 0,97 | 0,1,2 | 0,107 | 0,1,2 | 0,93 | 0,1,2 | 0,93 | ||

Variable | a3_{h} |
a3_{r}-1 |
a3_{p}-1 |
a3_{r}-2 |
a3_{p}-2 |
a3_{r}-4 |
a3_{p}-4 |
a3_{r}-5 |
a3_{p}-5 |
a3_{r}-8 |
a3_{p}-8 |
a3_{r}-9 |
a3_{p}-9 |

Domain | 0-9 | 0,1,2 | 0,93 | 0,1,2 | 0,33 | 0,1,2 | 0,79 | 0,1,2 | 0,162 | 0,1,2 | 0,7 | 0,1,2 | 0,124 |

Variable | a4_{h} |
a4_{r}-1 |
a4_{p}-1 |
a4_{r}-3 |
a4_{p}-3 |
a4_{r}-8 |
a4_{p}-8 |
||||||

Domain | 0-9 | 0,1,2 | 0,21 | 0,1,2 | 0,79 | 0,1,2 | 0,5 | ||||||

Variable | a5_{h} |
a5_{r}-3 |
a5_{p}-3 |
a5_{r}-9 |
a5_{p}-9 |
||||||||

Domain | 0-9 | 0,1,2 | 0,162 | 0,1,2 | 0,107 | ||||||||

Variable | a6_{h} |
a6_{r}-2 |
a6_{p}-2 |
a6_{r}-10 |
a6_{p}-10 |
||||||||

Domain | 0-9 | 0,1,2 | 0,97 | 0,1,2 | 0,3 | ||||||||

Variable | a7_{h} |
a7_{r}-1 |
a7_{p}-1 |
||||||||||

Domain | 0-9 | 0,1,2 | 0,48 | ||||||||||

Variable | a8_{h} |
a8_{r}-1 |
a8_{p}-1 |
a8_{r}-2 |
a8_{p}-2 |
a8_{r}-3 |
a8_{p}-3 |
a8_{r}-4 |
a8_{p}-4 |
||||

Domain | 0-9 | 0,1,2 | 0,17 | 0,1,2 | 0,107 | 0,1,2 | 0,7 | 0,1,2 | 0,5 | ||||

Variable | a9_{h} |
a9_{r}-2 |
a9_{p}-2 |
a9_{r}-3 |
a9_{p}-3 |
a9_{r}-5 |
a9_{p}-5 |
||||||

Domain | 0-9 | 0,1,2 | 0,93 | 0,1,2 | 0,124 | 0,1,2 | 0,107 | ||||||

Variable | a10_{h} |
a10_{r}-2 |
a10_{p}-2 |
a10_{r}-6 |
a10_{p}-6 |
||||||||

Domain | 0-9 | 0,1,2 | 0,93 | 0,1,2 | 0,3 | ||||||||

Variable | a1_{h} |
a1_{r}-3 |
a1_{p}-3 |
a1_{r}-4 |
a1_{p}-4 |
a1_{r}-7 |
a1_{p}-7 |
a1_{r}-8 |
a1_{p}-8 |
||||

Value | 3 | 0 | 0 | 0 | 0 | 1 | 48 | 2 | 0 | ||||

Variable | a2_{h} |
a2_{r}-3 |
a2_{p}-3 |
a2_{r}-6 |
a2_{p}-6 |
a2_{r}-8 |
a2_{p}-8 |
a2_{r}-9 |
a2_{p}-9 |
a2_{r}-10 |
a2_{p}-10 |
||

Value | 0 | 1 | 33 | 0 | 0 | 0 | 0 | 1 | 93 | 1 | 93 | ||

Variable | a3_{h} |
a3_{r}-1 |
a3_{p}-1 |
a3_{r}-2 |
a3_{p}-2 |
a3_{r}-4 |
a3_{p}-4 |
a3_{r}-5 |
a3_{p}-5 |
a3_{r}-8 |
a3_{p}-8 |
a3_{r}-9 |
a3_{p}-9 |

Value | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 1 | 7 | 0 | 0 |

Variable | a4_{h} |
a4_{r}-1 |
a4_{p}-1 |
a4_{r}-3 |
a4_{p}-3 |
a4_{r}-8 |
a4_{p}-8 |
||||||

Value | 3 | 0 | 0 | 0 | 0 | 2 | 0 | ||||||

Variable | a5_{h} |
a5_{r}-3 |
a5_{p}-3 |
a5_{r}-9 |
a5_{p}-9 |
||||||||

Value | 2 | 0 | 0 | 2 | 0 | ||||||||

Variable | a6_{h} |
a6_{r}-2 |
a6_{p}-2 |
a6_{r}-10 |
a6_{p}-10 |
||||||||

Value | 2 | 0 | 0 | 2 | 0 | ||||||||

Variable | a7_{h} |
a7_{r}-1 |
a7_{p}-1 |
||||||||||

Value | 4 | 2 | 0 | ||||||||||

Variable | a8_{h} |
a8_{r}-1 |
a8_{p}-1 |
a8_{r}-2 |
a8_{p}-2 |
a8_{r}-3 |
a8_{p}-3 |
a8_{r}-4 |
a8_{p}-4 |
||||

Value | 2 | 1 | 17 | 0 | 0 | 2 | 0 | 1 | 5 | ||||

Variable | a9_{h} |
a9_{r}-2 |
a9_{p}-2 |
a9_{r}-3 |
a9_{p}-3 |
a9_{r}-5 |
a9_{p}-5 |
||||||

Value | 1 | 2 | 0 | 0 | 0 | 1 | 107 | ||||||

Variable | a10_{h} |
a10_{r}-2 |
a10_{p}-2 |
a10_{r}-6 |
a10_{p}-6 |
||||||||

Value | 1 | 2 | 0 | 1 | 3 | ||||||||

Specific problem instances are included in this benchmark and are linked to on the main benchmark page. Problems can also be generated using the following parameters:

- An area with length
*x*and width*y*in which to place the devices. - A number
*n*of devices. - A maximum power
*p*at which each device can broadcast at. - A path loss exponent
*exp*, which is the rate at which the radio signal attenuates.

Each device is placed randomly in the area. To determine the power required for two devices a1 and a2 to communicate with each other, first calculate the distance, *d* between the devices: *d = √((x2-x1) ^{2} + (y2-y1)^{2})*. The energy used (

This problem is related to the Travelling Salesman Problem (TSP) and Minimum Spanning Tree (MST) problem. The key difference with the TSP is that in MEB the salesman/broadcast can travel more than one route out of a city/node. The difference with the Minimum Spanning Tree problem comes from the fact that the cost of broadcasting to multiple child nodes is the maximum cost over all the links to children as opposed to the sum of the links.