Research and Reviews - International Journals

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Mixed Scheduling Coupled With Power Control and Routing for Wireless Adhoc Networks

A.Vidya, N.Tamilselvi
  1. Lecturer, Department of Computer Science, Park Maritime Academy, Kaniyur, Coimbatore, India
  2. Assistant Professor, Department of Computer Science, Dr.N.G.P Arts and Science College, Coimbatore, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

In ad hoc networks the communication between mobile nodes are done through wireless channel. Here the connections between mobile nodes are made without the infrastructure support such as base station. A power assignment for the links changes the network topology and thus scheduling is affected. Scheduling determines the link activation and interference and hence the power changes at each link should satisfy the SNIR requirements. In our proposed approach we employ both link scheduling and power control to manage the interference. Here we have assumed a TDMA based wireless ad hoc network where one of the nodes has receiver and other has transmitter, all other nodes occupy different time slots. In our scheduling algorithm priority is given to the links with larger queue which helps in blocking traffic to neighboring links. Also we have studied the scheduling with power control and scheduling without power control mechanisms and found that scheduling with joint power control achieves significantly larger throughput and less delay at the cost of slightly higher energy consumption. In routing the minimum energy route has to be selected at the beginning of the network operation to save energy. But in some cases for general and arbitrary topologies, bandwidth requirement may not be satisfied by scheduling alone, and hence, congestion occurs at some links in the network. In our algorithm, routes are selected using Ant Colony based routing considering QoS factors according to both energy consumption and the traffic accumulation. Our simulation results show that there is a trade-off between energy consumption and the network performance.

Keywords
MANET; Power Control; Scheduling; Routing; energy efficient algorithm; network lifetime

INTRODUCTION
Ad hoc networks are one of the wireless network types and are a collection of mobile nodes that form a temporary network. This finds classical application in battlefield communications, disaster recovery, and search and rescue operations. In an ad hoc wireless network, connections among mobile nodes occur via multihop wireless connections without the support from a fixed infrastructure such as a base station. Due to the mobility of nodes, the status of a communication link is a function of the location and the transmission power of the source and destination nodes [1]. Several transmitter-receiver pairs can communicate without the help of fixed infrastructure [2]. Structure of Ad hoc network is given in the fig.1.
Wireless networks allow users to access services and information electronically irrespective of their geographic positions. Due to this remarkable feature wireless networks are becoming more popular in computing industry. Wireless networks are classified into two types: one is infrastructure network which behave as routers that helps in discovery and maintenance of routes of all other nodes available in the network. In each node the information about other nodes are updated frequently and are consistent in table driven routing protocol whereas in On-Demand routing protocol, the routes are selected and allocated as per the requirement.
When a source needs to send a packet to destination, it first invokes the route discovery process to find the destination. In past few decades several routing algorithms have been proposed [3, 5]. The motivation behind our work has two major reasons 1) To improve wireless link volatility in design of higher layer protocols. i.e. Link Scheduling. 2) Introducing non- conflicting transmission as per SINR constraint. Thus multiple access problem is solved in two stages that search set of users along their path of transmission powers. In the first stage scheduling algorithm eliminate the interferences of independent users in wireless adhoc networks. This cannot be done by power control. Power control is made to executed in various methods for determining admissible power factor which can be used by other users to satisfy their single hop transmission requirements [4].
The remainder of this paper is structured as follows Section II describes the related work done in this area. Section III gives the proposed algorithm, Section IV gives the algorithm of the approach followed by experimental results in Section V and Conclusion and future work in Section VII.

RELATED WORK
In [6] author has compared the performance of two on-demand reactive routing protocols namely DSR and AODV. It has been inferred that pacing dropping rate for DSR is very less than DSDV and AODV thus indicating the high efficiency. In terms of mobility AODV and DSR performs well than DSDV. In [7] authors have found that in an dynamic environments the routing is a tedious task in MANET. The wireless links can go down due to the mobility of nodes and interference also they are error prone. In [8] authors have used terrain blockage model to evaluate power control loop similar to the CDMA networks. Cost of communication has been reduced by using ad hoc networks since it does not need power sources such as electricity grid. It is also shown that power control improves energy consumption and throughput by 10-20% and 15%, respectively. In [9] Multi-commodity flow variable has been formulated for rate constraint, scheduling constraint and resource allocation in networks with fixed wireless channels as a utility maximization problem with constraints.
In [10] authors have formulated a dynamic routing algorithm in which when the host movement occurs the algorithm automatically adapts to its routing changes. The proposed protocol works well in environment conditions such as host density and movement rates. In [11] author have studied the COMPOW (Common Power) and CLUSTERPOW (Cluster Power) protocols for power control in homogeneous and non-homogeneous networks. Power control is a method used for transmission of the packets at an optimized power level such that it increases the traffic carrying capacity and reduce the batter usage power and it minimizes the interference to improve the overall performance of the system. In [12] author have proposed a routing protocol which increases the network life time in cellular systems since ad hoc networks works in limited battery energy.
In [13] diversity back pressure algorithm have been modified in a such a way that packet whose backpressure metric is higher is allowed to transmitted and is forwarded to the link that has largest differential backlogs. This is in contrast to DIVBAR in which each receiving nodes stores and accumulates the received packet in separate partial packet queue. Hence the probability of successful repetition is possible during retransmission. In [14] author had stated that collision free channels provide contention resolution to form the dimensionality for the nodes. Collision avoidance schemes attempt to eliminate collision that degrades the network performance. But this cannot prevent collision of signal packets from fading and capture effects on the channel. In [15] author had proposed an online algorithm which is fully distributed algorithm that solves the channel assignment, routing and scheduling.

CASE STUDY
A. Types of Scheduling algorithms and Power Control Strategy
It is inferred from the scheduling rules that power control is coupled with scheduling process because it affects the SINR criterion. We have three alternative ways to handle coupling
• Power allocation before scheduling
Based on the SINR requirement power is allocated to each link individually against the noise interference and stays fixed. The links are then made to maximize number of links that transmits at same time by satisfying SINR requirements. This technique is termed as simplified scheduling since there is no real power control.
`• Joint power control and scheduling
This algorithm works by scheduling and power controlling at the same time. Whenever a new link is added to the activation set, the power is updated when scheduling is going on. Our proposed algorithm is similar to this category.
• Scheduling before power control
At first scheduling is allowed to take place for finding the maximum number of links that can be activated at the same time and then the power levels are assigned for those link activation set for satisfying SINR requirements. There may be chances that SINR requirements may not be satisfied. For this type of situation the activation set are adjusted and power allocation is tried again.

MIXED SCHEDULING COUPLED WITH POWER CONTROL AND ROUTING FOR WIRELESS ADHOC NETWORKS
A. Network Model
Wireless ad hoc network does not need a fixed infrastructure since the nodes are connected through wireless channels. In TDMA based networks all other nodes present shares the same time slot and same frequency band. Assumptions made are given below.
Here it is assumed that the users are known with a good time slots and no multiuser detection is made.
For network control a separate low data rate channel and overhead traffic are exchanges for the scheduling and routing implementation.
Each node has a transmitter and receiver in which transmitting and receiving cannot occur at same time.
Time slots are assumed to be directed links. Each node may be in one of the states transmitting or receiving and may be active or idle. The network model is given in fig 2.
Here our aim is to avoid the complexity and frames a new cross layer protocol design and introducing a scheduling and routing algorithms. Computationally intensive power control is to be executed in distributed fashion in order to reduce the communication. The parameter setting is shown in the table 1.
Routing becomes a major issue in MANET because of the mobility of nodes in wireless channel. Routing is the transfer of information from source to destination. Complexity I routing increases due to the characteristics such as dynamic topology, limited energy and resources. Quality plays a major role in providing wireless access to information. The path between source and destination should be chosen appropriately to satisfy the user requirements. Biological inspired algorithm may serve as a solution for developing routing in MANET‟s.
B. Network Routing Using ACO
Network topology varies frequently and traffic load arises due to time varying nature of wireless networks. This distributed nature is matched by the multi agent nature of ACO algorithms. The network can be represented as a DAG graph where the vertices correspond to the router set and the links are connectivity between the nodes in routers. Now routing is the problem that finds a minimum cost path for the nodes in the corresponding DAG which is done by ant colony algorithm.
Characteristics
• Multipath routing and traffic adaptive network routing
• Passive and active information gaining
• Stochastic component usage
• It does not allow the local solution to create a global impact
• Less selfish way in deciding shortest path schemes which favors load balancing.
• Limited sensitivity to parameter settings.
C. Algorithm
1. Form link metric covering all links that have traffic and define the activation as empty set.
2. Try iterative power control algorithm with the lowest metric link added to the activation set.
3. Select a source node S that has to send data to a destination D with QoS requirements higher transmission rate, less delay and more bandwidth. A list of nodes that are progressively visited by the ant is called visited nodes list. This list forms the route R from the source node to destination node.
4. Initially choose the source node S. The visited nodes list will be initialized to source node (S).
5. S initiates a Path_Request_Ant to destination D through all its neighbors which are in 1-hop distance from S. The Path_Request_Ant contains source address, destination address, hop count and bandwidth.
6. After that the pheromone evaporation of all the 1- hop distance nodes will be calculated. Each node (i) maintains a table called “PMtab” a table of Pheromones specifying the quantity of available pheromone on each link (Vi, Vj). This quantity is initialized to constant C.
7. Then we calculate the pheromone evaporation of all the 2-hop distance nodes.
8. At last we calculate the path preference probability value of each path from source S with the help of pheromone evaporation of every node. A node j from a set of adjacent nodes (j, k… n) of i is selected as MPR node such that it covers all the 2-hop distance nodes and its path preference probability is better than others.
9. If calculated path preference probability value is better than the requirements, the path is accepted and stored in memory.
10. When the Path_Request_Ant reaches the destination, it will be converted as Path_Reply_Ant and forwarded towards the original source. The Path_Reply_Ant will take the same path of the corresponding Path_Request_Ant but in reverse direction.
11. The path with higher path preference probability will be considered as the best path and data transmission can be started along that path.
12. Check if SINR of this routing link is not satisfied or SINR of any of the links are not satisfied remove this particular link from the link set and return to step 2.
13. IF SINR of this and its associated links are satisfied add this link to activation set and remove this link block and other links blocked by this link
14. Repeat the steps 2to 12 until the link set becomes empty.
D. QoS Evaluation
Let us assume a DAG graph such as G=(V,E) which represents a mobile ad hoc network, here V represents the set of network nodes and E represents the bi-directional links. To find the shortest path the ACO relies on the pheromone laid by the ants across the link. The amount of pheromone deposited is same on any link (Vi, Vj) along the route R. global quantity function of a route R is denoted by Δτ (Vi, Vj). It is expressed with the following equation
equation
where,
• B(R) = min(B(Vi, Vi+1), B(Vi+1, Vi+2), . . . , B(Vk − 1, Vk)); The smallest link bandwidth in route R while Vi is the source node and Vk the destination node.
•T(R) = min((T(Vi, Vi+1), T(Vi+1, Vi+2), . . . , T(Vk − 1, Vk)); The smallest link expiration time in route R.
• D(R) = D(Vi, Vi+1)+ D(Vi+1, Vi+2), . . . + D(Vk − 1, Vk); The sum of delays on all links in route R.
• βB, βT and βD denote the link weight factors that show the relative significance of each QoS parameter during pheromone update on a route R.
Even though the pheromone is deposited on the link, its amount of quantity (equation 1) is only defined after finding the route. It permits to appreciate in the same way all links forming the route. Nevertheless, the local quality of a link is taken into account in its choice. This local quality represents the heuristic factor or the visibility of the ant. It is given by the following equation:
Equation
where αB, αT and αD are parameters showing the relative importance of each QoS parameter during the link selection. The pheromone quantity on the link (Vi, Vj) is:
Equation
where ρ is the evaporation factor (0 < ρ < 1). It is used to avoid the infinite increment of pheromone on the link that may lead to stagnation route. When an ant searches for a route, it chooses probabilistically one node among its neighbour‟s nodes that are not visited yet. The routing probability value between Vi and Vj is computed by the composition of the strength of pheromone values (equation 3) and the visibility values (equation 2).
Equation
where:
• τ (Vi, Vj) is the amount of pheromone on the link (Vi, Vj).
• ηi,j is the visibility of the link (Vi, Vj).
• α and β are two parameters that show the relative significance of the pheromone and the visibility during the process of QoS route discovery.
• M: is the set of all possible neighbor nodes Vk, not visited yet by the ant.

SIMULATION RESULTS
We study the algorithm to evaluate the performance gain of the mixed algorithm, and to provide a reference point for the future distributed version. It is also applicable to some networks that might have a base station. The simulation is a packet-level simulation code written in language Java. We assume that the maximal transmission distance is 4 units and the maximal power is 256. Packets are generated by Poisson process at each node pair independently. We assume large buffer size Qmax at all nodes (packets are discarded if the buffer is full). Packets are failed if the SINR is not satisfied due to the inaccurate power calculation because of the finite number of iterations. We first simulate the simple 5 node network. We use routing parameter (.9, 0.1) to show the different performance of the scheduling algorithms. scheduling 1 is the simplified algorithm, scheduling 2 is the joint scheduling and power control algorithm and scheduling 3 is our mixed algorithm.
As explained above, if we use the minimum energy route, then all the traffic will go through node 0, and only one link could be active at any slot, and therefore, different scheduling algorithms make no difference. We notice that there is a threshold rate for each of the scheduling algorithms. If the rate is larger than the threshold rate, then the number of waiting packets keeps increasing until the buffer is full and packets are dropped. When the rate is larger than the threshold, the throughput no longer increases with the same slope, and the delay increases rapidly. The threshold rates for the three scheduling algorithms for this specific network are about 0.04, 0.08, and 0.06 (packets/slot/source– destination pair) respectively. We find that scheduling algorithm 1 has smallest throughput (and threshold rate) and largest delay. It is clear that the joint power control and scheduling improves the network performance significantly in terms of throughput and delay. Comparing scheduling algorithm 2 and 3, it is clear that our joint algorithm outperforms the joint algorithm based on [4] in both throughput and delay. The average power of the algorithm 1 does not change significantly as the rate increases, because the power is preset, and is not related to the interference caused by a higher rate. On the contrary, the joint scheduling and power control algorithms use more power for larger rate. The reason is that more interference is generated when more links are active, and therefore larger power is needed to overcome the interference and satisfy the SINR requirements. The routing table provides information regarding the destination, next hop and the power level at which the transmission is taking place. The comparison of three algorithms in terms of rate and throughput are shown in fig 3.

CONCLUSION AND FUTURE WORKS
In this paper we have proposed a centralized algorithm of joint power control, scheduling and routing. Our simulation shows that there is a trade-off between energy consumption and the throughput and delay network performance. This work has several possible extensions. The specification of a distributed algorithm and its evaluation is one of them. The algorithms can also be easily modified to accommodate multiple flow types. The only modification needed is to use bf, f = 1,2,. . . ,F, instead of b, when checking SINR requirements in the case of F flow types. For some applications, it may not be possible to do scheduling for each slot; we may attempt scheduling for a frame consisting of multiple slots. The basic ideas remain the same. Finally this study can be extended to CDMA-based systems by slightly changing the scheduling rules and by reflecting the CDMA sequence properties on the value of the SINR threshold.

Tables at a glance
Table icon
Table 1
 

Figures at a glance
Figure 1 Figure 2 Figure 3
Figure 1 Figure 2 Figure 3

References