048: Minimum Energy Broadcast (MEB)

Proposed by David A. Burke, Kenneth N. Brown

Overview

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.

Distributed COP Formulation

To formulate the problem as a Distributed COP, we have an agent, a_i, representing each device in the network. The neighbours of a_i include all agents that a_i can communicate with when broadcasting at its maximum power level.

Relationship variables: For each neighbour a_j, a_i has a public variable, taking one of 3 values, indicating the relationship between the two devices in the current solution (broadcast tree):

0 = the devices are not connected in the broadcast tree
1 = a_i is the parent of a_j in the broadcast tree
2 = a_i is the child of a_j in the broadcast tree

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 maximum of these costs.

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.

Example

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.

**Table 1.** Complete list of variables and domains of all agents in the problem. Variable names begin with the agent name. Subscript ‘h’ indicates hop count variable; ‘r’ indicates relationship variable; ‘p’ indicates broadcast power/energy cost variable. For relationship variables, -x indicates that variable is for the relationship with agent x. Similarly for energy cost variables, the -x indicates that this is the power required to reach agent x.
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

**Table 2.** Optimal assignment of values to variables in example problem. Cells in green indicate when an agent will broadcast to another agent. Cells in yellow are the broadcast power required by that agent to broadcast to all its children in the broadcast tree. The optimal solution is the sum of all these values, i.e. 275.
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

Problem Parameters

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)² + (y2-y1)²). The energy used (w=watts) to broadcast this distance is: w = (d^exp) x 0.0001. If w < p, then the devices can communicate.

Notes

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.