Market Based Strategy

Market-based topology management

The MBS described here intends to create and maintain well-dened wireless mesh network architectures in a exible and dynamic way. The technique in fact has the power to change the whole behavior of the network by adjusting a small set of parameters, without the need for special equipment or complex protocols. We base our solution on the economy laws of supply and demand to dynamically organize the network. The rst law of supply and demand states that when demand is greater than supply, prices rise and when supply is greater than demand, prices fall. The power of such forces, rise and fall, depends on how great the dierence between supply and demand is. The second law of supply and demand, then, states that the greater the dierence between supply and demand, the greater is the force on prices. The third law states that prices tend to an equilibrium point, where the supply is equal to the demand [57]. If we align our main objectives with the laws of supply and demand we will see that these three laws map perfectly to the main requirements of a topology management algorithm. We may map our need to control the number of clusters to the rst law of supply and demand. Controlling the prices of each kind of service oered in the network, we can control the number of elements oering such service. The second objective is to have a fast convergence to a stable state. This requirement is met by applying the second law, since the bigger are the dierences among supply and demand the faster is the convergence. Finally, recall that our third objective is to maintain an well balanced and as stable as possible network, while respecting the desired architecture. Clusters should not only have roughly the same size but we should have an easy way to control and ne tune that size. Cluster heads must be able to optimally handle the communication among nodes inside their clusters and exchange key information with neighboring nodes fast and eciently. However, the optimal number of nodes per cluster depends upon many factors, such as number of attendees and agencies involved, kind of disaster and environmental conditions. These issues are covered by the third law, since the nal topology is expected to be a Pareto optimal arrangement [112] and hence it should be stable and fair among all the participants. Figure 8.1 presents these relationships schematically. The basic mechanism of the evaluated protocols is as follows: whenever an IN arrives in the network, it broadcasts a connection request for the nodes nearby. This request is answered by all the MR/RN/CH in the region. The neighboring nodes answer with their status, number of connections and link status. This information is used to dene a connection cost to each one of the possible sponsor nodes. The information in the answer packets and the cost function determine to which node the IN will attach. The cost policy states that, considering all the given data, the lowest cost sponsor should be chosen. To increase the network stability a node just gives up being a CH or a RN if it moves and loses all its connections, or if it moves and enters in conict with other well established, lower cost, CH/RN in the region. A node should always try to attach to the node that presents the lowest attachment cost. To decrease the number of CHs, the chosen basic connection costs should give greater priority to CHs in detriment of the other kind of nodes. Only if there are no CHs around or they are completely overloaded should an IN decide to attach to a MR or a RN and become a new CH. Similarly, to promote a more homogeneous load balance, the cost function guarantees that an IN node will always attach to the least loaded, or the best suited sponsor. Algorithm 4 describes in further details the method when maintaining the CHORIST network architecture.

Experiments for the MBS topology control 

Environment

 The evaluations were made using Sinalgo simulator [96] in a 2Km2 area. We vary the number of nodes and the communication range of the nodes. All experiments were conducted using Linux Fedora Core release 6 in an Intel Xeon 1.86GHz machine with 16GB of RAM. All graphs are presented with a condence interval of 99% and each point is the result of the mean of 34 runs with dierent network congurations. The nodes arrive randomly and are placed uniformly over the observed area. As the experiments observed in 114 Chapter 8 Market Based Strategy Section 7.4, the centralized implementation works as an oracle: its results are the best possible ones and unachievable with distributed algorithms. However, this oine implementation shows us how far the proposed algorithm is from the theoretical minimal CH optimal solution. All experiments were conducted for dierent communication ranges of 50, 100, 150, 200, 250, and 300 meters. However, as the nal results for these variations did not present any meaningful dierence, we will present only the values obtained for the 200 meters communication range experiments. To evaluate the adaptability capacity of the proposed solution we dened different network congurations and node costs. Considering the implemented cost formula 8.1, if one needs, for example, a network with fewer CHs, it is only a matter of decreasing the basic CH connection cost and increasing the costs for other kind of nodes. In this way nodes will prefer to attach to an existing CH, as it is cheaper than to attach to other nodes to create a new CH. For each dierent target scenario the cost values should be adapted accordingly to the nal desired network shape. We created six dierent scenarios with dierent basic costs for each type of nodes. The basic cost congurations used in the experiments were: • Conguration 1: favors the creation of clusters, as much as possible. It has high cost to connect to a cluster and low cost for connecting to other nodes. The basic connection cost values (β) are CH=20, MR=5, RN=1. • Congurations 2 to 5: are variations over the standard conguration, smaller costs for attaching to CHs and larger ones for RNs and MRs. The objective of testing these congurations is to establish whether small variations of costs aect the algorithm behavior. β values are:  Conguration 2 CH=0, MR=2, RN=1  Conguration 3 CH=0, MR=5, RN=3  Conguration 4 CH=0, MR=7, RN=5  Conguration 5 CH=0, MR=20, RN=5 • Conguration 6: tries to shape the network as close as possible to the minimum WCIDS, the target conguration of the implemented oine approach. For this case values are: CH=0, MR=50, RN=45. Congurations 1 and 6 are diametrically opposite in the sense that the rst aims to stimulate the creation of CHs while the second aims to keep the 8.5 Experiments for the MBS topology control 115 number of clusters as small as possible. The dierences among the congurations and the desired nal network shape are expressed by the histograms in Figure 8.2. These histograms were created from typical runs of the simulation. We can observe that the technique really manages to control the network topology going from the extreme case of a nearly minimum number of CHs to the case where almost all nodes are CHs.