Abstract
Abstract-We propose a distributed power management algorithm that decides on an optimum coverage area for individual node to preserve network connectivity, reduce interference thus improve network performance with changing environment and network topology. In order to be strongly connected in the network, a node may increase its power indiscriminately causing interference. Since interference is one of the major problems in wireless network, the proposed algorithm will co-operatively reduce inter-node interference in the network. Uni-directional links are also a major source of interference as most of the routing protocol only utilizes bidirectional links. So, the algorithm will attempt to prevent such links or if required convert them into bi-directional links.
We will show that the algorithm provides strongly connected and more reliable network over dynamic physical channel modeled by log-distance path loss model, log-normal shadowing model and rayleigh fading model. We will show that the proposed algorithm stabilizes node connectivity over the dynamic network and environment and even, to a certain extent, prevent node from being completely disconnected from the network. Further, it reduces interference and improves network performance.
Index Terms-Mobile ad hoc networks, distributed power management algorithm, routing protocol, interference, unidirectional link, bi-directional link, physical propagation model. 1
The topology of a network and the performance of routing protocol in mobile ad hoc networks significantly deteriorate with the dynamic attenuating environment [1] . The coverage area of a node or the propagation distance of the signal is limited by propagation loss and fading losses due to reflection, diffraction, scattering and multipath. These losses are estimated by propagation models. We will model the propagation loss by log-distance path loss model, the random shadowing effects by log-normally distributed fading loss and small-fading loss and the doppler effect by rayleigh
INTRODUCTION
The topology of a network and the performance of routing protocol in mobile ad hoc networks significantly deteriorate with the dynamic attenuating environment [1] . The coverage area of a node or the propagation distance of the signal is limited by propagation loss and fading losses due to reflection, diffraction, scattering and multipath. These losses are estimated by propagation models. We will model the propagation loss by log-distance path loss model, the random shadowing effects by log-normally distributed fading loss and small-fading loss and the doppler effect by rayleigh This work is based on research partially supported by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-00011. This work is based on research partially sponsored by the U.S. Air Force Research Laboratory under agreement FA8750-09-1-0158. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. fading model. Thus, the propagation environment determines the coverage area of a node and its connectivity.
These propagation and fading losses determine the Signal to Noise Ratio (SNR) and the Bit Error Rate (BER) of a communication link. In reality, multi-user networks are interference-limited rather than noise-limited. Interference from other nodes in the network can be more significant than background noise. Therefore, we will consider Signal to Interference and Noise Ratio (SINR) to determine the BER of a communication link [2] .
The proposed algorithm is generic network layer power management algorithm and does not use special functionality of any routing protocol. Therefore, it can be applied to any routing protocol. Different routing protocols such as Dynamic Source Routing (DSR) in reference [3] , Any Path Routing without Loops (APRL), Ad hoc On-Demand Distance Vector (AODV), On-demand Multicast Routing Protocol (ODMRP) and System-and Traffic-dependent Adaptive Routing Algorithm (STARA) in reference [4] have been used by the authors to prove their concept. To demonstrate the performance and the capability of the proposed algorithm, we have applied it to Optimized LinkState Routing (OLSR) protocol as an example of a typical routing protocol.
In this paper, we will show that the proposed distributed power management algorithm adapts well in dynamic network topology and physical environment and provides a more reliable and strongly connected network. The related works in power control are listed in Section 2. Section 3 describes the proposed distributed power management algorithm. Propagation models are surveyed and the reasons for selecting log-distance path loss, log-normally distributed shadowing and rayleigh fading models are stated in Section 4. A brief description of OLSR protocol is presented in Section 5. Section 6 presents the simulation parameters and results and Section 7 concludes the paper.
RELATED WORK
Power control algorithms in literature have been studied as techniques to improve network connectivity and energy efficiency. Most of the approaches studied are to find a complete set of transmission power for the nodes with the purpose to minimize the total power consumption [5] [6] . Because mobile ad hoc networks do not have any central scheduler, such centralized approaches are not applicable.
Another approach is to preserve network connectivity by assigning optimal transmit power for the nodes. Two distributed algorithms LINT and LILT are proposed in reference [7] which adjust transmission powers to maintain desired node connectivity. The algorithms, however, are reactive schemes and use Carrier Sense Multiple Access (CSMA), as a multiple access technique to evaluate their performance. COMPOW and CLUSTERPOW [5] [8] set the smallest power required to maintain each node's connectivity. These algorithms, however, find the smallest common power level at which the network is still connected. The problem with common power is that some nodes in the network could be in a highly dense area with very high connectivity and some might be in a low dense area even disconnected from the network.
Another approach is the Cone-Based Topology Control (CBTC) [9] where each node transmits with minimum power such that there is at least one neighbor in every cone of the angle centered at the node. In Minimum Spanning Tree (MST) based algorithm [10] , each node builds its local MST independently and only keeps on-tree nodes that are one-hop away as its neighbor.
These power control algorithms do not adapt to the changes in environment and network topology.
DISTRIBUTED POWER MANAGEMENT
ALGORITHM We propose a dynamic distributed power management algorithm that optimizes node transmit power and minimizes inter-node interference in the network.
Consider a network of n nodes in an area A. If P i (t) and represent the transmitting power and connectivity of node i in the network at time t, then select subject to the following constraints: 1. The node should have at least minimum connectivity, , i.e. minimum acceptable number of neighbors with which the node has a bi-directional link with at any time t.
2. For a packet from node j to node i to be correctly detected, SINR must be greater than a threshold, .
(
The node should not transmit at such a high level that it causes interference to other nodes in the neighborhood. Specifically, the algorithm will try to minimize the inter-node interference as shown in equation 3. If a node has high node connectivity, then it can probably afford to decrease its power level and still maintain acceptable connectivity. Let be the maximum number of neighbors allowed i.e. the upper acceptable connectivity threshold. This has an advantage of decreasing inter-node interference in the network.
3. The transmit power for the nodes should be more than the minimum power level, but less than the maximum power level, defined by network and node power specifications.
4. The algorithm also tries to conserve node's battery capacity,
, which is one of the important design considerations for mobile ad hoc networks. The algorithm will only allow the nodes to increase their power level if their battery power is higher than the critical battery power level, (6) We assume that each node has no knowledge of other node's transmission power level. The algorithm is illustrated in a flowchart shown in figure 1 .
Every node in the network continuously checks its connectivity, interference level and its battery capacity. We will assume that each transmitter has no knowledge of other node's power level.
If node i connectivity, , is less than the minimum acceptable node connectivity, , it will attempt to improve its connectivity by increasing power level. It can only increase its power level if its current power level, , is lower than the maximum power level, . It checks if there are any uni-directional links from other nodes. If there are, it will try to build bi-directional links with those potential neighbor nodes. It increases its by an increment, α, and checks after a short time delay, τ short_delay . If there are no unidirectional links to the node, then it should try to construct bidirectional links with other nodes which are not already its neighbors. The node can only create a uni-directional link by increase its , so it's equality important for the potential neighbor to try to establish a link with it too. So, the node increases its and sends out a PowerLevelUp_Request request. It then waits for medium time delay, τ medium_delay to check if it managed to set up any new link. Since it is trying to construct link with nodes that are not its neighbors, the maximum hop count for PowerLevelUp_Request is set at 2. It should not be set too high because nodes transmitting at high power level can interfere nearby nodes. Thus, it will eventually select the lowest power level that will create bidirectional link. Now if the node moves in to a dense area, it can probably afford to decrease its and still maintain acceptable network connectivity. This has an advantage of reducing inter-node interference in the network. So, if is higher than the upper connectivity threshold, , it decreases its and checks its after τ short_delay . It also decreases its if its battery capacity, , becomes less than the . It, thus, effectively selects the lowest to keep the node well connected with at least . A node i will transmit PowerLevelDown_Request to other nodes if it is suffering from interference. It sets the maximum hop count for the request to 2 to prevent forwarding overhead. It also sets Request_TTL (Time To Live) so that older requests are ignored.
If a node receives a PowerLevelDown_Request, it will decrease its if its is in a higher acceptable range. If it changes its , it checks its after τ short_delay . Otherwise, it waits for a long time delay, τ long_delay, to avoid excessive calculations and overhead from frequent changes in .
If a node i receives a PowerLevelUp_Request, it increases its only if its is in the lower acceptable range. It then waits for τ short_delay to check its .
A node will forward other node's requests if the hop count of the request is more than 1 and the Request_TTL is still valid.
If at any instance the node's is not sufficient, i.e. less than , it will reduce its to maintain minimum connectivity, . The algorithm is in a sense greedy because achieving lowest connectivity is given the highest priority.
WIRELESS PROPAGATION MODEL
Propagation model estimates the average received signal at a given distance from a transmitting node in presence of propagating and fading losses. Most of the simulations done in mobile ad hoc networks employ either the trivial disk propagation model, the free space propagation model or the two-ray propagation model [11] .
The disk propagation model does not take the physical channel into consideration. Free space propagation model considers a clear Line of Sight (LOS) path. The two-ray propagation model considers both the direct and a ground reflected propagation path between the source node and the destination node. It is, therefore, not suitable in case of mobile ad hoc networks where there are several multi-paths of similar strength and the propagation range is limited by the node transmission capability.
We will, therefore, use the log-distance path loss propagation model to model the propagation loss in mobile ad hoc wireless channel. The average path loss of the propagation signal in this model is expressed as a function of the distance and the path loss exponent, , is given by equation 7 [11] [12] . (7) Propagation environment dictates the value of . indicates the rate at which the path loss increases with distance.
This fading loss at a particular location due to shadowing effects is random and log-normally distributed as shown in equation 8 [13] . (8) Different versions of signal wave, because of reflecting objects and scatterers, combine in the receiving antenna to form a resultant signal that might widely vary in amplitude and phase, depending on the distribution of the intensity and relative propagation paths. The fading loss, P Fading , used to model this small-scale fading and doppler effect due to multipath. In this paper, we will consider flat fading model which has a Rayleigh distribution probability density function (pdf) given by equation 9 [12] , (9) The Random Waypoint Mobility model (RWMM) [14] is used to model the node's mobility. In this mobility model, node selects a random destination within the roaming area and moves towards it at a speed between predefined minimal and maximum set value. After the node reaches destination, it stops for a predefined pause time and then randomly selects another destination and moves towards it. This node mobility behavior is repeated throughout the simulation.
The propagation model, therefore, determines the Signal to Noise Ratio (SNR) at the receiving node. We will model the multi-user network as interference-limited rather than noiselimited. Therefore, the Signal to Interference and Noise Ratio (SINR) given by equation 2 is used to determine the BER for a communication link [2] .
The SINR or the BER determines the quality of the link and if the link can be selected for routing packets.
OPTIMIZATION LINK-STATE ROUTING
PROTOCOL OLSR optimizes the classic link state protocol by using only selected nodes called Multipoint Relay (MPR) to advertise links in the network [15] . Each node selects MPRs such that it has a bidirectional link to all of its two-hop neighbor nodes. Only MPRs are allowed to advertise the links by periodically broadcasting Topology Control (TC) messages. Neighbors, who are not selected as a MPR, receive and process the broadcast message but do not forward it. This technique of using MPR substantially reduces the message overhead.
The HELLO message maintains the local link and neighborhood information in the network and is used in selecting MPRs. The topology information from the HELLO and TC packets are used to construct routes in the network.
SIMULATION PARAMETERS AND RESULTS
The performance of power management algorithm is analyzed here through simulations carried out in OPNET network simulator [16] .
The network consists of 100 nodes distributed over a 1000 meter by 1000 meter area. All the nodes are configured with OLSR and IEEE 802.11 MAC protocol. Each node, transmitting at 15dBm, always has packet of average size of 1024 bits to send. The simulation is conducted over urban area such as a city characterized by no LOS path but multiple versions of the signal due to many obstacles such as buildings and trees in the propagation path. We will model this environment by typical value for of 3.2 and standard deviation of 4.0 dB. The node mobility is modeled with a minimum speed of 0 m/s and maximum speed of 3 m/s to simulate a pedestrian environment.
A link in this paper is defined as acceptable if the power of the signal in the receiving node is greater than the threshold value of -95 dBm in accordance with the 802.11 standard. All multi-user interference is treated as noise. If the power level of the signal in the receiving node falls below the threshold, the link is considered bad and is discarded. Only the good links are considered when routing the packets through the network.
The parameters of the power management algorithm: minimum and maximum connectivity, minimum and maximum power level and the time delays are all design considerations. We have conducted numerous simulations on this model over a wide range of these parameters. We have analyzed the impact of these parameters and its sensitivity on the network topology and performance.
However, to evaluate performance and capability of the algorithm in this paper, we have selected typical values for node connectivity of 6 and 8 for the lower threshold, , and upper threshold, . Similarly, the minimum and maximum transmission power levels, and , are set at 5 mW and 100 mW. The node can select the power level between and at an increment, α, of 5 mW. The time delays: τ short_delay , τ medium_delay , and τ long_delay are set to 5, 10 and 15 seconds. The initial transmission power level for all the nodes is set at 15dBm (approximately 30mW).
Node connectivity fluctuation of a typical node in the network over the period of simulation with and without power management algorithm is shown in figure 2 . Without the power management algorithm, it is clearly seen that node connectivity initially increases to 20. It then steadily decreases as the node moves to a low node density area becoming totally disconnected from the network around 750 to 800 seconds. Throughout the simulation, node connectivity of a typical node in the network severely fluctuates even becoming disconnected from the network.
In case of power management algorithm, as node connectivity increases beyond the higher connectivity threshold, it decreases it's transmit power to approximately 5 mW clearly evident in figure 3 . Similarly to earlier case, the node moves to an area with low node density and its node connectivity starts decreasing. The power management algorithm, however, realizes that node connectivity has decreased below the lower connectivity threshold and starts increasing it power level to 100 mW. The node with the power management algorithm does not even get disconnected from the network at any point during the simulation. It is clear from figure 2 and 3 that node adjusts its power level between 5 mW to 100 mW to maintain acceptable network topology. Figure 2 and 3 highlight the variation in routing parameter because of changes in environment and the network. Nodes in the network should adapt to variations in the environment and the network to provide strongly connected and more reliable network thereby improving routing performance.
The distribution of node connectivity of all the nodes in the network with and without power management algorithm is shown in figure 4 . Connectivity of node without power management algorithm was found to be distributed from 0 to 25 with more than 2% of the node totally disconnected. However with power management algorithm, approximately 46% of the nodes have acceptable connectivity with less than 0.1% of the nodes totally disconnected from the network at any time during the simulation. Figure 5 shows the distribution of transmit power level of the nodes in the network. 57% of the nodes have its power level less than the initial power level of 15 dBm with 7% of the node at the highest power level of 100 mW.
It is clear from figure 2 that routing protocol with power management algorithm reduces node connectivity and topology fluctuations and therefore decreases routing overhead as evident in figure 6 .
Further, in the work presented in reference [17] we have shown that under similar simulation environment the algorithm increases the network throughput by as much as 37%. The algorithm was also found to increase average node power from 15dBm to 19.37dBm. This intuitively implies an increase in inter-node interference. However, the average noise interference was found to decrease by about 2dBm with this algorithm even though the average node power increased by 4.37dBm. This is because the power management algorithm keeps a check on inter-node interference by not letting the nodes increase their power indiscriminately.
CONCLUSION
We have shown that the proposed distributed power management algorithm adaptively preserves network connectivity, increases network performance and reduces interference with the dynamic environment and network topology. The proposed algorithm is generic network layer power management algorithm and can be applied to any routing algorithm. To demonstrate its performance and capabilities, we have applied it to OLSR as an example of a typical routing protocol. It does not utilize any functionality specific to a particular protocol such as OLSR in this case. It is clear from figure 2 that node connectivity of a typical node in the network severely fluctuates from 0 to 20 even becoming disconnected from the network for a significant period of time during the simulation. Figure 2 and figure 3 show that the network adapts better to the changes in the physical environment and network topology with the power management algorithm. It reduces node connectivity fluctuations even preventing node, to a certain extent, from being totally disconnected from the network. Thus the proposed algorithm provides strongly connected and more reliable network. It also lowers inter-node interference and routing overhead consequently increasing network performance.

{'paper_id': '11688024', 'title': 'Topology control using distributed power management algorithm for mobile ad hoc networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:11688024', 'source': 'S2ORC'}