Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees

Description

We investigate the problem of constructing a multicast tree in ad-hoc networks. In particular, we address the issue of the power consumption, that is, the overall energy that the stations must spend to implement such a tree. We focus on two extreme cases of multicast: broadcast (one-to-all) and unicast (one-to-one). Minimum Spanning Trees (MSTs) and Shortest-Path Trees (SPTs) yield optimal solutions for broadcast and unicast, respectively. Unfortunately, they do not guarantee any optimality for the "counterpart", that is, MSTs are non-optimal for unicast, while SPTs are non-optimal for broadcast.

We experimentally evaluate the performances of an algorithm combining MST solutions with SPT ones. Our approach is based on the construction of Light Approximate Shortest-path Trees (LASTs) of a given directed weighted graph, introduced by Khuller et al [1995]. LASTs approximate simultaneously the cost of the MST and the distances of the SPT rooted at a source node, thus yielding, also in the worst case, optimal solutions for both unicast and broadcast.

The algorithms evaluated have been implemented in Java. The evaluations have been made on random instances following two different objectives: (i) evaluate the LASTs in terms of total power consumption w.r.t. the MSTs, (ii) evaluate the LASTs in terms of unicast tree selecting the "farthest" pair of stations in the Euclidean instances randomly generated.

A more deepest description of the experiments and the obtained results have been included in the following paper:

P. Penna and C. Ventre.
Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees.
In the Proc. of the 1st ACM Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN 2004), ACM, pag. 61-68, 2004.

Instructions

The source code can be found here. In the file you will find the following structure:

EvaluatingLAST.zip
|
+--MyCode
| |
| |-GraphFrame.java -- Stand alone application source code
| |-GraphFrame.class -- Stand alone application class file
| |-EvalLAST.java -- Applet source code
| |-EvalLAST.class -- Applet class file
| |-... -- working classes
|
|-LastApplet.html -- HMTL example for the Applet
|-pathConf.txt -- path of the computed experiments files
|-readme.txt -- results files formats

As you can see the program runs as stand alone application or as web applet. The code is organized in a package called MyCode. You can compile the .java files with a simple javac command from the directory you unzip the file (in the example C:\YourFavoriteDirectory in a Windows machine):

C:\YourFavoriteDirectory> javac MyCode.ClassName.java

or simply start the application with the java intrerpreter command from the directory you unzip the file:

C:\YourFavoriteDirectory> java MyCode.GraphFrame

If you want to start the applet you can open with your favorite browser the file LastApplet.html. You can also see the running applet here.
Upon started the (stand-alone) application will present you as follows:



Since the program has been written in Java it runs on Windows or Unix-like operating systems. It takes as input the parameters of the problem: the number of nodes of the instance to generate, the signal attenuation parameter and the approximating SPT factor for the LAST (called delta). (Further details in the paper.) In the bottom part of the window there are the computed trees of the given random Euclidean instance (showed in the top of the window).

We give here a little explanation of every graphic command:

nodes sliding bar :

The number of nodes of the Euclidean random instance to generate. Each node is assigned a random position in the 300x300 square.
Range: 1, ..., 350.

source node combo box:

After a random instance is generated you can change the index of the source node (default source has index 0) to have a more interesting instance. You can check the index of a node simply positioning the mouse on the interested node in the area Original Graph. In this area the source node is yellow and there is a label to identify it.
Range: 0, ..., #nodes - 1.

Attenuation parameter combo box:

You can decide to change the signal attenuation parameter to every value (even not integer) you want. We recall that in the empty space the attenuation parameter is 2. We test our sotfware only for reasonable little values. We do not know what it happens for "unreasonable" values.
Tested range: 0, ..., 100.

Delta LAST tree sliding bar:

Whit this parameter you can decide which SPT (rooted at source) approximation factor the LAST Tree must ensure. Choosing a value near to one you want to be very close to a SPT (i.e., you change more edges from the MST).
Range: 1.01, ..., 5.00.

Throw again button:

This command will create a new random instance with the selected parameters.

Farthest pair button:

This command will calculate the worst pair of nodes for the instance w.r.t. the unicast. The obtained results will be stored in the file farthestPairSlow.txt created in the path specified in the file pathConf.txt provided with the source file. The format of the file is specified in readme.txt.
In particular the computation is as follows: the selected nodes are the pair in which the ratio between the path in the MST and the direct edge is maximum. The ratios stored are, in this case, lastpath/newsptpath and mstpath/newsptpath, where: (i) lastpath is the length between the selected nodes in the LAST, (ii) mstpath is the same thing for the MST, (iii) newsptpath is the length of the path between the selected pair of nodes in a new SPT rooted in one of them.
The selected pair is showed in the Original graph area coloring light blue them. The results are also shown in the Notes area. A different calculation will be done with the fast option selected.

Fast checkbox:

Checking this option the farthest pair computation will be faster then described above. In particular we calculate the maximum among the ratios lastpath(source, u)/sptpath(source, u) and the maximum among the ratios mstpath(source, u)/sptpath(source, u) for every u in the nodes. The ratios will be stored in farthestPairFast.txt. The nodes maximizing the ratios will be showed in Original graph area as above.

Trials commands:

In this area you can choose to make several trials computing the values you need. In particular in the combo box you can select for which computation you need the results: (i) wireless cost, (ii) farthest pair, or (iii) both of them.

Wireless cost button:

This command will calculate the wireless cost of the three trees. The results will be stored in WirelessBroacastCost.txt. The results are also shown in the Notes area.

Options:

Store nodes checkbox: with this option the coordinates of the instance nodes will be saved in the results files.
Insert your graph button: you can insert in a proper way the coordinates of your favorite graph.

Examples

• Inserting a star

  Click on the Insert your graph button and insert the following string:

  (150,150):(300,150):(299,163):(298,177):(295,190):(290,203):
  (285,215):(279,227):(271,238):(263,249):(254,258):(244,267):
  (233,275):(221,282):(209,288):(196,293):(183,296):(170,299):
  (157,300):(143,300):(130,299):(117,296):(104,293):(91,288):
  (79,282):(67,275):(56,267):(46,258):(37,249):(29,238):(21,227):
  (15,215):(10,203):(5,190):(2,177):(1,163):(0,150):(1,137):
  (2,123):(5,110):(10,97):(15,85):(21,73):(29,62):(37,51):(46,42):
  (56,33):(67,25):(79,18):(91,12):(104,7):(117,4):(130,1):(143,0):
  (157,0):(170,1):(183,4):(196,7):(209,12):(221,18):(233,25):
  (244,33):(254,42):(263,51):(271,62):(279,73):(285,85):(290,97):
  (295,110):(298,123):(299,137):(300,150):(165,150):(165,151):
  (165,153):(164,154):(164,155):(164,157):(163,158):(162,159):
  (161,160):(160,161):(159,162):(158,163):(157,163):(156,164):
  (155,164):(153,165):(152,165):(151,165):(149,165):(148,165):
  (147,165):(145,164):(144,164):(143,163):(142,163):(141,162):
  (140,161):(139,160):(138,159):(137,158):(136,157):(136,155):
  (136,154):(135,153):(135,151):(135,150):(135,149):(135,147):
  (136,146):(136,145):(136,143):(137,142):(138,141):(139,140):
  (140,139):(141,138):(142,137):(143,137):(144,136):(145,136):
  (147,135):(148,135):(149,135):(151,135):(152,135):(153,135):
  (155,136):(156,136):(157,137):(158,137):(159,138):(160,139):
  (161,140):(162,141):(163,142):(164,143):(164,145):(164,146):
  (165,147):(165,149):(165,150)
  

  It should appear the following graph:

  

• Calculate wireless cost and farthest pair for the previous graph

  Simply click on the proper buttons. The results are shown in the Notes box.