Abstract: The power supply for mobile nodes is in general limited by the capacity of the batteries. It is therefore crucial to design algorithms and protocols that reduce energy consumption. In this study, we present Power Minimization Algorithm in Wireless Ad-hoc Networks Based on PSO for Throughput Enhancement to determine the neighbor selection and power level assignment so that we can maintain the connectivity by the congested nodes. We have also conducted experiments by simulations, which show that the performance of the proposed algorithms outperform those of the existing ones.
INTRODUCTION
Mobile Ad hoc Networks (MANETs) are gaining increasing popularity nowadays since they not only play an important role under the disorganized or hostile settings, but they posses potential applications in all traditional areas of interest for mobile computing. Each node in a MANET has a limited energy resource (battery) and each node operates in an unattended manner. Consequently, energy efficiency is an important design consideration for these networks.
The power supply for mobile nodes is in general limited by the capacity of the batteries. It is therefore crucial to design algorithms and protocols that reduce energy consumption.
There are two approaches to achieving less energy consumption; the Topology control approach emphasize on scheduling the node in the network to enter into sleep mode to reduce the total energy consumption of the network as a whole (Ramanathan and Hain, 2000; Singh and Raghavendra, 1998), But in the power control approach, nodes are allowed to coexist and interfere with each other. Based on the ambient interference level, each node determines its own transmission power to ensure successful transmission. Many algorithms have been proposed by ElBatt and Ephremides (2004), Kawadia and Kumar (2003) and Muqattash and Krunz (2003) to integrate power control. The goal of such algorithms is to select an appropriate transmission power level for each frame, based on the perceived network status.
Power saving and power control mechanisms are two well known mechanisms to improve power efficiency. The basic idea of power saving mechanism is to let the wireless interface of a station be turned off while the station is not going to communicate with other stations during a certain period of time. For ad hoc WLANs, IEEE 802.11 Spec. (IEEE Std 802.11-1999) provides a power saving mechanism. In addition to IEEE 802.11, there are also some researches paying their attention on power saving issue (Jung and Vaidya, 2002; Bononi et al., 2001). The related data of power control can be found by Monks et al. (2000) and Muqattash and Krunz (2004).
In this study, we propose Power Minimization Algorithm in Wireless Ad-hoc Networks Based on PSO for Throughput Enhancement. The overall goal of this algorithm is to determine the neighbor selection and power level assignment so that we can maintain the connectivity by the congested nodes. We have also conducted experiments by simulations, which show that the performance of the proposed algorithms outperform those of the existing ones.
PROBLEM FORMULATION
We can first formulate PMA problem as follows: Given a mobile ad hoc network with a set of n mobile nodes N = {N1, N2, …, Nn} equipped with omni antenna or directional antenna including Ki (for node Ni) sectors, each of which can operate at one of m different power levels P = {p1, p2, …, pm}, how to adaptively assign each node a suitable power level (for each of its sector), PA = {p (i,k)| power level assigned to Ni at its kth sector} such that the overall load for the deduced graph.
The equality constraints can be automatically satisfied by load calculation, while the lower/upper limit of control variables corresponds to the coding on the PSO algorithm, so the inequality constraints of the control variables are satisfied.
Objective function:
| (1) |
Constraints:
In the forementioned statement, the load function can be defined as:
| (2) |
The measurement of the load of node i, should take not only the loads of its neighbors but also the load of the nodes which is interfered by this node. These two parts have different level for node load, α is used for this purpose. Through MAC information the traffic load of each node can be measured.
An attenuation function Atten is given:
| v | = | The attenuated value. |
| t | = | The time passed by. |
Then the load measurement function for Nj Blank Neighbor (Ni):
| (3) |
| Tstart (i, j) | = | The start time of node Nj. |
| T now | = | The current time, Kj is the number of sectors of node Nj. |
Next, Busy function is given as follows:
Where, Pt(i, k) is the power level for different interference effect, for example, if the kth sector of node Nj is directed to node Ni, the Pt (i, k) is given the highest power level. Pt (I, k) function for directional antenna can be defined as follows:
| (4) |
We can perform the distributed topology control for MANET at each node based on the load function and the process will be event-driven when the node request from upper application or its neighbor for new route to the destination and time-driven during which the network topology remain unchanged until time expires.
Particle swarm optimization (PSO algorithm): The basic elements of the PSO techniques are briefly stated as follows:
In a PSO algorithm, the population has n particles that represent candidate solutions. Each particle is a k-dimensional real-valued vector, where k is the number of the optimized parameters. Therefore, each optimized parameter represents a dimension of the problem space (Laskari et al., 2002). The PSO technique for integer problem can be described in the following steps.
Step 1: (Initialization): Set t = i = 0 and generate random n particles, {Xj(0), j =1, 2,..n). Each article is considered to be solution for the problem and it can be described as Xj(0) = [ xi,1(0); x i,2 (0); ......; x i,k(0)]. Each control variable will have a range [x min, x max]. Each particle in the initial population is evaluated using the objective function f. In this paper, the objective function is the load of each node in the network.
Step 2: Counter Updating: update the counter i = i +1.
Step 3: Velocity updating: Using the global best and individual best, the jth particle velocity in the jth dimension in this study (integer problem) is updated according to the following equation:
| (5) |
From the previous equation i is the iteration number, j is the particle number and k is the kth control variable. Then, check the velocity limits. If the velocity violated its limit, set it at its proper limit. The second term of the above equation represents the cognitive part of the PSO where the particle changes its velocity based on its own thinking and memory. The third term represents the social part of PSO where the particle changes its velocity based on the social-psychological adaptation of knowledge.
Step 4: Position updating: Based on the updated velocity, each particle changes its position according to the following equation:
| (6) |
Step 5: Individual best updating: each particle is evaluated and updated according to the update position.
Step 6: Search for the minimum value in the individual best and its solution has ever been reached so far and considers it to be the minimum.
Step 7: Stopping criteria: if one of the stopping criteria is satisfied, then stop otherwise go to step 2.
ALGORITHMS DESCRIPTION
As mentioned earlier, each node will interact with routing protocol and invoke Power Minimization Algorithm locally driven by event or time expiration.
According to the interaction results from routing protocol and the power control, the invoke type of power control can be divided into two classes; in class one nodes will keep the neighbor information for a period of time in cache and will not perform power control unless the cache expires and in class two, nodes will perform power control when they received route request. The combination of the two classes can integrate our implementation into the routing protocol.
In the first class, a node N will invoke power control only when it receives a route request and it has passed the time period t since the last power adjustment.
In the second class, the node only can invoke a power control when it is requested rout action. This is to avoid frequently invalidating the established routes. For example, in a route N1-N2-N3 If after reducing transmission range for N1 or N2 a new route has to be established between N1 and N3 since the link between N1 and N2 is broken, in this case the routing overhead will introduce consequently.
In Fig. 1a each Node initiates a neighbor request packet using a maximum power level. The existing routing protocols all have a neighbor discovery mechanism; we do not directly use it here, because most of such routing protocols only discover bidirectional neighbors, while with power adjustment it is common to have unidirectional neighbors.
When a neighbor receives request packet as shown in Fig. 1b, each node replies with an acknowledgment packet with the highest power level to ensure this reply can be received by the sender.
| Fig. 1: | The broadcast request process in an ad hoc network |
Finally, the node N determine the power level after receiving the first neighbor reply packet from a neighbor and keep receiving as many as possible replies before determining which is the suitable power level to assign as shown in Fig. 1c. A neighbor waiting timer is set for N to avoid waiting the neighbors reply and ignores any later replies. Next, the node N performs the normalized load based scheme to determine the power level of N based on the information it collects. Present algorithm can select those neighbors with minimal total costs while keeping the network connectivity as well such that improve the overall end-to-end throughput.
SIMULATION RESULTS
Simulation environment: This simulations are implemented in Network Simulator (NS-2) (NS, 2004) from Lawrence Berkeley National Laboratory (LBNL) with extensions for wireless links form the Monarch project at Carnegie Mellon University. The simulation parameters are as follows:
| • | No. of nodes: 20 ~70. |
| • | Testing field: 1000 χ1000 m. |
| • | Packet size: 512 bytes. |
| • | Power levels: 5. |
| • | Tx range: 250 m. |
| • | Mobile speed: with uniform speed chosen between 0-5 m sec‾1 with 2 sec pause between each suc cessive movement and the simulation is run for 400 sec. |
| Fig. 2: | Throughput comparison in the base case of no power control, the degree based only scheme and the power control mechanism |
Analysis of results: All packets had the size of 512 bytes. For each configuration of the simulation environment, we experimented with two cases, the power control mechanism with the combined power assignment scheme and the base case of no power control where each node was assigned with the default maximum power to cover the 250 m transmission range. We were mostly interested in the throughput metric. In order to obtain a conceivable comparison result, we repeated the measurement 100 times over 100 randomly generated node mobility scenarios. Since all packets had the same size and the source route headers added by AODV are considered as overhead, in this simulation, we measured the overall end-to-end throughput by counting the successfully received packets at the destination nodes.
Figure 2 shows the change of the overall end-to-end throughput. The No Power Control curve is for the base case of no power control. The Degree-Based curve is for the degree based only scheme. And the With Power Control curve represents the power control mechanism with after applying the power optimization algorithm. The throughput was improved significantly in all cases. The gain resulted from the more spatial reuse because of less channel interference.
It can be seen that the improvement ratio decreases while the network density is getting larger because the interference in a very dense network has been already high even if nodes select lower power. We think the cross-layer collaboration instead of pure power adjustment will alleviate it and expect our approach can help a minimum-interference routing protocol to establish routes more favorable to the throughput.
CONCLUSION
In this study we present Power Minimization Algorithm in Wireless Ad-hoc Networks Based on PSO for Throughput Enhancement to determine the neighbor selection and power level assignment so that we can maintain the connectivity by the congested nodes. We have also conducted experiments by simulations, which show that the performance of the proposed algorithms outperform those of the existing ones.