Energy Efficient Network Reconfiguration Algorithm Based on Cooperation for Wireless Ad hoc Network: A Survey

Energy Efficient Network Reconfiguration Algorithm Based on Cooperation for Wireless Ad hoc Network: A Survey

Energy Efficient Network Reconfiguration Algorithm Based on Cooperation for Wireless Ad hoc Network: A Survey

Mr. Sachin Kumar Soni 1, Mr. Gajendra Singh 2

1M.Tech Scholar SSSIST Sehore (M.P.)

2HOD CSE Department SSSIST Sehore (M.P.)

Abstract In a wireless multi hop ad hoc network, communication between distant nodes is done via intermediate hops working as forwarders. As forwarding the data packets consumes energy, intermediate hops may not wish to cooperate in communication. In this paper we are dealing with two major issues of wireless ad hoc network namely, cooperation and energy efficiency. We propose an algorithm that increases the level of cooperation of a wireless ad hoc network in an energy efficient manner, working over topology control in network along with load balancing and sleep scheduling

Keywords Ad hoc networks, cooperation, energy efficiency, load balancing, sleep scheduling, topology control.

1. INTRODUCTION

   A WIRELESS ad hoc network is an infrastructure less, decentralized network. It has no central object to govern the functioning of the network. In this network, each node also known as hop may act as router, forwarder, source and/or destination for a data packet. As compared to wired networks, ad hoc networks are more prone to malicious attacks and different kinds of failures. In order to manage the functionalities of an ad hoc network the nodes in it must be cooperative. Non-cooperative behavior of nodes affect throughput of the network.

   In ad hoc network nodes communicate with each other by relaying data packets for other nodes when there is no direct link in between. To carry out this communication successfully the nodes must show their cooperation in relaying the packets. However, as nodes in ad hoc network have limited energy associated with them, they may choose not to forward any or all the packets for other nodes. But this misbehavior will consequently reduce the overall network throughput. Detection and penalization of misbehaving nodes is done by a protocol named CONFIDANT [3]. It detect malicious nodes by means of observation or reports about several types of attacks, thus allowing nodes to route around misbehaving nodes and to isolate them [3].

   A wireless ad hoc network has finite energy, so to save energy and to increase the lifetime nodes may choose not to cooperate in relaying packet. This emphatically

   would bring down the throughput percentage. To manage the network in such a manner that the resources available, get properly utilized and nodes in the network do not drain out, energy efficient algorithms are needed. Along with it, sleep and wake-up strategy contributes to a level in saving a nodes energy.

   In this paper, we are trying to improve the level of cooperation, considering local topology control and load balancing, in an energy efficient manner with sleep scheduling working in parallel.

   The remainder of this paper is organized as follows. In Section II, we present related works on cooperation in ad hoc networks, topology control, load balancing and sleep scheduling. Section III includes formulated problem. Section IV includes proposed solution of the listed problem. In Section V, we will discuss the work to be simulated.

2. RELATED WORK

   The idea of this paper is all-embracing and do not particularly fall into one category of wireless ad hoc networks. It covers several issues such as cooperation, energy efficiency, load balancing, topology control and sleep scheduling.

   The idea of the project starts with cooperation in network and its measurement.

   1. Cooperation and its measurement

      Cooperative communication is a way to improve the performance of relay transmission system working over ever-challenging wireless medium. In this domain, the work did include strategies which mainly follow tit-for- tat in order to maintain cooperation among nodes. [1] Nodes are assumed to be rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. The optimal throughput that each node should receive is defined to be the rational Pareto optimal operating point. Using which a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT) has been proposed [2]. A market-based approach has also been worked upon in which nodes charge a price for

      relaying data packets and then use these incentives to relay their own packets. In both these approaches, the nodes which are detected as non-cooperating are punished either by isolating them from rest of the network or their packets are not forwarded by rest of the nodes.

   2. Energy Efficiency

      Energy is an important asset in ad hoc networks, as the working of whole network relies on the availability of energy. Energy efficiency can be achieved in many ways. The ways include [4] distributed algorithm where each node makes local decisions about its transmission power and these local decisions collectively guarantee global connectivity. Specifically, based on the directional information, a node grows it transmission power until it finds a neighbour node in every direction. The resulting network topology increases network lifetime by reducing transmission power and reduces traffic interference by having low node degrees.

   3. Load Balancing

      As Wireless ad hoc networks is infrastructure less, nodes working on their own in coordination with other nodes which makes them consume energy for being on the route of different Path in the network. Some of the nodes may act as forwarder or router in multiple numbers of paths while some may idle or do the minimal. These conditions create a huge difference between the residual powers of the nodes. They require a procedure where it is made sure that there will not be any particular set of nodes that only participate in communication but the network as a whole must participate. This comes under load balancing and different load balancing algorithms in theory choose different kind of parameters that are measured and balanced.

      By taking network node taking into account three factors, residual battery capacity, the number of hops on the path and the length of the interface queue which gives an estimate of load on a node, that is the average number of packets, queued up at the interface queue to be delivered to the destination. By estimating these values and averaging those over time give an approximate look of the traffic in the networks and energy left with nodes. These estimates are added in a manner such that the main contributing factor becomes hop count and average queue length when energy of the nodes is high and residual energy become the parameter of choice when energy gets depleted. The defined parameters are:

      1. Route Energy (RE): The route energy of a path is the

         minimum of residual energy of nodes (rei) falling on a route. Higher the route energy, lesser is the probability of route failure due to exhausted nodes.

      2. Traffic queue (tq): The traffic queue of a node is the number of packets queued up in the nodes interface. Higher is its value, more occupied the node is.

      3. Average Traffic Queue (ATQ): It is the mean of traffic queue of nodes from the source node to the destination node. It indicates load on a route and helps in determining the heavily loaded route.

      4. Hop count (HC): The HC is the number of hops for a feasible path

   4. Topology Contrl

      Topology control is defined as a process where the topology of a network can be controlled by selective addition of nodes and links within a network. Due to varied usage of wireless ad hoc network in number of applications like battlefield, environmental modeling, emergency relief, topology control in ad hoc networks becomes a primary challenge where nodes can change their transmitting powers and can select different nodes for forwarding data. Topology control is defined as a process where the topology of a network can be controlled by selective addition of nodes and links within a network

      The basic goal of Topology Control is

      • Maintain connectivity using the minimum transmission power.

      • Maintain connectivity by moving some router nodes to fill in the hole.

      • Enable nodes to self-organize themselves into clusters.

      • Load balance with power consideration.

   5. Sleep Scheduling

   Research results have shown that radio energy consumption of listening or idling in ad hoc networks can be significant. Hence by turning off the transceivers of idle devices or making nodes sleep, redundant energy can be saved more eciently. Node scheduling is an efficient power saving method but it is required to be in coordination with the routing algorithm. It should allow as many nodes as possible to turn their radio receiver off most of the time, since even an idle circuit can consume almost as much energy as an active transmitter. Also, it should forward packets between any source and destination with minimally more delay than if all the nodes were awake.

3. PROBLEM FORMULATION

   1. Assumptions

      Starting with a static ad hoc network with known topology, we assume that all the nodes are working as in Unit Disk Graph (UDG) i.e., with same initial energy. Nodes which are not busy being a forwarder or a source/destination will move to sleep mode from the active mode according to a sleep scheduling algorithm.

   2. Problem Definition

      For a static ad hoc network with known topology, the goal is to devise an algorithm that increases the cooperation level among the static nodes in an energy efficient manner.

   3. Problem Description

   At any instant of time, the number of nodes and the network topology is known. To increase the cooperation level, one of the factors which we have to consider is that the nodes in the network do not drain out too soon. For that, an energy efficient algorithm is to be applied and some techniques must be used which may save energy of a node when it is in idle condition.

   Initially, we are assuming the network with some number of nodes in sleep mode while other nodes in active mode and the network is in running state in which routing has already been done.

   We propose a technique which can increase the cooperation level in an energy efficient manner. Along with it sleep scheduling is running in parallel so that overall energy efficiency is increased. We have tried to resolve above stated upshots while deliberating issues like load balancing and topology control.

4. PROPOSED SOLUTION

   1. Assumptions

      The proposed protocol will run between two successive routing updates. And the messages in the network should get delivered in real time i.e., there should be no delay.

   2. Protocol

      Consider a static ad hoc network with known topology having N number of nodes, where in routing has already been performed. In the network, out of N nodes, some nodes are in sleeping state (say Ns) while the rest are active (say Na) (Figure 1). So,

      N = Ns + Na . (i)

      where,

      N = Total number of nodes

      Ns = Number of nodes in sleeping state Na = Number of nodes in active state

      Figure 1: Initial Topology of the Network

      (An example network with 20 nodes, where, 5 nodes numbered 1, 6, 10, 14 & 19 are in sleep mode while rests are awake.)

      The protocol requires value of the cooperation to be precompiled at every of the node. For that, we will be using queues. Each node in the network is working with two queues attached with them, which are:

   Cooperation of a node can be calculated using two queues associated with the nodes. Cooperation can be defined as number of packets forwarded by a node.

   Qi = Pf i + Pr Qo = Pf o + Po Pf o = Qo – Po

   Where

   Pf o = No. of Packets forwarded

   Po = No. of self generated packets sent Pf i = Packets to be forwarded

   Pr = No of packets of received packets

   Pf o indicates the level of cooperation.

   The protocol can be divided into five modules as following: Module 1: Two-hop Communication

   A hop is a component part of a signals journey from source to destination. When a data packet has to be transmitted, it often has to go after crossing many routers before it reaches final destination. Each time a packet is passed to next router hop count increases by 1. An ad hoc network uses two or more wireless hops to convey information from a source to destination. In particular, when only two hops are

   Node _ID	Cooperation Value	Status	Time to Sleep

   Node _ID	Cooperation Value	Status	Time to Sleep

   used, the communication is known as 2-hop communication.

   Module 2: Cluster Formation

   As the protocol starts each of the node distributes its level of cooperation in two-hop proximity. This is done through 2-Hop Prefatory Packet which carries the node_ID along with calculated cooperation value and energy remaining with the node.

   Figure 2: Two Hop Prefatory Packet

   every node receiving this message maintains a table structure to have track of cooperation level of every of its two hop neighbor. The node with highest level of cooperation becomes the cluster head. If the two nodes Are having same cooperation value then the cluster head will be elected on the basis of remaining energy. Each of the clusters contains all the nodes which are in two-hop connectivity with the cluster head. Also the clusters may be overlapping clusters.

   Figure 3: Cluster formation Module 3: Inflicting Penalty

   Each of the cluster head has some of the responsibilities associated with them. A cluster head has to:

   1. Monitor the cooperation level of every node in its cluster,

   2. Detect non-cooperative node and penalize them by forcefully sending them to sleep state for a certain period of time, and

   3. Find alternate paths when nodes are penalized.

   For this, every cluster head maintains a following table:

   Status field can have three values:

   1. Node is in active State.

   2. Node is forcibly sent to sleep state.

   3. Node voluntary sent to sleep state.

   It compares the value of cooperation of each node with every other and finds a node with lowest cooperation value. It then sends a Penalty Message to that node which includes TTS i.e. time to sleep.

   Figure 4: Penalty Message

   Module 4: Identification of New Route

   Whenever a node with lowest cooperation level is punished and is forcibly sent to sleep state, cluster head manages the topology of the network. Suppose if there is any path from source to destination which had the punished node, cluster head has to find an alternate path. This may infix two conditions:

   1. There may be one efficient path formed by active nodes. If it is so, then use it.

   2. There are more than one alternate paths. This may further introduce three situations:

      1. One of them is efficient out of all the paths. If so, then use it.

      2. None of them is efficient. I it is so, then use load balancing mechanism to create an efficient path.

      3. If no node is in the proximity and even load balancing could not find an efficient path, then in this case routing algorithm is triggered by the cluster head.

   Figure 5: Punished Nodes (Double concentric circled N are punished nodes-with low cooperation value)

   Module 5: Sleep Scheduling

   This module can be divided into two cases.

   Case I: When node voluntarily goes to sleep state-

   In ad hoc network it may happen that a node remains idle for a certain period of time. In that case, it voluntarily goes to sleep state to save energy. The fixed time interval after which node goes to sleep state is referred as Idle Time.

   Whenever a node sleeps it sends an Alert Message to its neighbors that include time for which node would be sleeping. This sleeping time is referred to as Sleep Interval.

   Figure 6: Sleep Alert

   When in sleep state, a node periodically checks its sleep buffer which stores the packets received when the node is asleep. Sleep buffer is actually input queue but in case of sleeping nodes, we are referring it as sleep buffer. This periodic interval is named as sleep buffer checking interval.

   Requesting to cooperate:

   It may happen that during topology control and load balancing i.e., while identifying a new route any sleeping node may be required to act as intermediate hop. For that, cluster head sends request to the required hop. The request gets stored in the sleep buffer of the node.

   But as adverted before that the clusters are overlapping, a sleeping node may receive requests from multiple cluster heads. This problem is resolved on first come first serve basis.

   Figure 7: Requesting message (In this message the data part contains the requesting message)

   Case II: When node is forcibly sent to sleep state-

   The node with lowest cooperation value is punished and is forcibly sent to sleep state

   When a punished node completes its punishment it sends an introductory packet to every node informing its availability.

   Figure 8: Introductory packet (In this message the data part contains a message indicating availability of the node)

5. SIMULATION

The protocol designed will be simulated in NS2 with the above drawn topology and testing the requirements of being called an energy efficient algorithm. The nodes will increase gradually as the network goes bigger.

REFERENCES

1. Vikram Srinivasan, Cooperation In Wireless Ad Hoc Networks.

   Department of Electrical and Computer Engineering, University of California at San Diego..

2. Peter Marbach, Member, IEEE, and Ying Qiu, Cooperation in Wireless

   Ad Hoc Networks: A Market-Based Approach.

3. Sonja Buchegger, Performance Analysis of the CONFIDANT Protocol

   (Cooperation Of Nodes: Fairness In Dynamic Adhoc Networks). IBM

   Zurich Research Laboratory Saumerstrasse, Switzerland.

4. Roger Wattenhofer, Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. Microsoft Research

   Redmond, WA 98052

5. C. Siva Ram Murthy, B. S. Manoj, Ad Hoc Wireless Networks, Architectures and Protocol. Prentice Hall Communication Engineering and Emerging Technologies series.

6. E.L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi,

   Algorithmic Aspects of Topology Control Problems for Ad hoc Networks, MOBIHOC 02, June 9-11, 2002, EPFL Lausanne, Switzerland, ACM, 2002.

7. N. Li and J. Hou , Design and Analysis of an MST-Based Topology Control Algorithm.

8. Vamsi Paruchuri, Shivakumar Basavaraju, Arjan Durresi, Rajgopal Kannan and S.S. Iyengar, Random Asynchronous Wakeup Protocol for Sensor Networks. Louisiana State University, Department of Computer Science