Correct predictions are in blue. If we detect only a subset of a labelled sentence, we highlight the caught part as blue, the missing part light blue. False positives are in green and false negatives are in red.

Problem 048 (Minimum energy broadcast) — Constraint detection

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 -LRB- MEB -RRB- 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 -LRB- a broadcast tree is formed -RRB- . The desired configuration is that which minimises the total energy required by all devices , thus increasing the lifetime of the network . Several approaches -LRB- both centralised and distributed -RRB- 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 -LRB- DisCOP -RRB- is one appropriate way to model and solve the problem , and it is this approach that will be described in this specification . DisCOP Formulation To formulate the problem as a DisCOP , we have an agent , ai , representing each device in the network . The neighbours of ai include all agents that ai can communicate with when broadcasting at its maximum power level . Relationship variables : For each neighbour aj , ai has a public variable , taking one of 3 values , indicating the relationship between the two devices in the current solution -LRB- broadcast tree -RRB- : 0 = the devices are not connected in the broadcast tree 1 = ai is the parent of aj in the broadcast tree 2 = ai is the child of aj 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 ai 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 . 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 = radic -LRB- -LRB- x2-x1 -RRB- 2 + -LRB- y2-y1 -RRB- 2 -RRB- . The energy used -LRB- w = watts -RRB- to broadcast this distance is : w = -LRB- dexp -RRB- x 0.0001 . If w > p , then the devices can communicate . Notes This problem is related to the Travelling Salesman Problem -LRB- TSP -RRB- and Minimum Spanning Tree -LRB- MST -RRB- 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 .

Problem 048 (Minimum energy broadcast) — Detection of the decisions and objects to be modeled

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 -LRB- MEB -RRB- 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 -LRB- a broadcast tree is formed -RRB- . The desired configuration is that which minimises the total energy required by all devices , thus increasing the lifetime of the network . Several approaches -LRB- both centralised and distributed -RRB- 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 -LRB- DisCOP -RRB- is one appropriate way to model and solve the problem , and it is this approach that will be described in this specification . DisCOP Formulation To formulate the problem as a DisCOP , we have an agent , ai , representing each device in the network . The neighbours of ai include all agents that ai can communicate with when broadcasting at its maximum power level . Relationship variables : For each neighbour aj , ai has a public variable , taking one of 3 values , indicating the relationship between the two devices in the current solution -LRB- broadcast tree -RRB- : 0 = the devices are not connected in the broadcast tree 1 = ai is the parent of aj in the broadcast tree 2 = ai is the child of aj 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 ai 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 . 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 = radic -LRB- -LRB- x2-x1 -RRB- 2 + -LRB- y2-y1 -RRB- 2 -RRB- . The energy used -LRB- w = watts -RRB- to broadcast this distance is : w = -LRB- dexp -RRB- x 0.0001 . If w > p , then the devices can communicate . Notes This problem is related to the Travelling Salesman Problem -LRB- TSP -RRB- and Minimum Spanning Tree -LRB- MST -RRB- 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 .

Back to list