Node Discovery Based on Energy-Distance Factor in MANET

Node Discovery Based on Energy-Distance Factor in MANET

Jailani Kadir, Osman Ghazali, Suhaidi Hassan InterNetWorks,

Universiti Utara Malaysia, Sintok, Kedah Darul Aman, Malaysia

Abstract

Residual energy on a node is among the factors that contribute to the prolonged of the wireless network connection lifetime. The nodes on MANET are usually consists of a battery with limited storage and processing capabilities. Another limitation is when the battery is situated in areas where it is not possible to re-charge. This may hinder the achievement of optimum route connection in extending the network lifetime. To address this problem, the probability based method (PMNS) is proposed in selecting a node during a path discovery. The scheme combines the interrelated energy level with the distance factor of the energy routing protocol on the nodes. The analysis shows that the PMNS scheme can prove that the probability of selecting a node with the highest residual energy as the primary path followed by a lower residual energy nodes as an alternative route. In addition, the node with the largest value is preferable compared to the other nodes to be the next hop in the direction of the destination.

1. Introduction

   Mobile ad hoc networks (MANET) consist of wireless nodes that form a communication network without fixed infrastructure. Topology changes that occur in MANET are due to node mobility or node that breaks down as a result of running out of power. The nodes in the network have different battery levels. The power on the nodes is often referred as size, model, property, or capacity due to various battery manufacturing techniques that yield different capacities and decay rates, which will definitely affect the nodes connection. In the concept of MANET, a node can function as a router to connect to a remote node of a source. The nodes connection in a network requires an effective routing mechanism to ensure service quality (QoS). Therefore, the condition of a node becomes an important issue to be considered in selecting a node in

   a routing protocol due to the limited energy of n node that depleted during packet forwarding.

2. Background

   To maintain the optimum lifetime of a routing path in a network that consists of nodes with limited energy is a very challenging task. This is due to the fact that the node in MANET has limited power or energy depending on its batterys size, model, property, and capacity. The nodes activities, such as transmission, reception, and overhearing, will decrease the energy of the battery [1]. The reduction of energy will cause transceiver delay and overhead cost. Eventually the node will break down when the energy runs out. Nevertheless, the network lifetime can be preserved longer with efficient nodes energy management using appropriate techniques of nodes selection, energy conservation, and energy consumption minimization. To achieve an optimum network lifetime connection, the route discovery process must start with the node selection process. Recent research demonstrates the limitations of the existing algorithms and techniques in a particular route discovery sessions of a routing protocol. If a weak node with limited energy strength is allowed to form a route, the energy will drain earlier and eventually break the connection path.

3. Routing protocol in MANET

   The routing protocol refers to the process of moving packets through an internetwork, such as the internet. Routing consists of three phases: i) Node discovery with participating node; ii) Disjoint or non-disjoint route discovery; and iii) Route maintenance. There are two types of routing techniques; the first is single path and the other is multipath. The single path routing is established from a single route path from source to the destination nodes, while the multipath technique allows the establishment of several numbers of routes path from source to the destination nodes, which can

   provide route suggestions or alternative route. The multipath routing effectively reduces the frequency of route discovery. This will cause the latency for discovering another route is reduced when the current route is broken. The multiple paths can be useful in improving the effective bandwidth of communication, responding to congestion and heavy traffic, and increasing delivery reliability [2]. Alternatively, traffic can be distributed among multiple routes to enhance transmission reliability, provide load balancing, and secure data transmission. However, these techniques cannot ensure the sustainability of the node connection since the energy factor is not considered.

4. Characteristic of node with constrain energy

   Each node in MANET serves as host and router which are supplied with battery power. Depletion of the battery power of the node in the routing path will decrease the network lifetime connection. Due to the difficulties of charging or replacing the battery of the node, the energy management and energy consumption are vital in ensuring the extension the node lifetime. The limitation of the energy source of the nodes in MANET is the most challenging problems [3-4]. The nodes in a MANET are usually battery powered that predetermined their time making capabilities. The only practical way of achieving connection lifetime optimization is by developing an efficient routing algorithm scheme instead of modifying additional capacity.

   The nodes use energy each time beacon signals are sent to the neighboring nodes to detect its existence or each time data is sent to the desired destination. The mobile nodes in MANET cannot operate without energy. The limited battery power of mobile nodes is considered as one of the constraints in an ad hoc network operation. Each time a node transmits, receives or overhears through a communication medium, it consumes energy. The standard IEEE

   802.11 protocol, which is developed for a wireless network with a little traffic, has wasted so much energy due to the following causes [3]: idle listening, collision, overhearing, and protocol overhead.

   The limited battery lifetime imposes a severe constraint on the network performance. Thus, the residual energy at nodes is significant in determining the selection to prolong the network lifetime. Nodes in a route path with minimum energy will quickly drained which will then effect the network connection. Therefore, the factor that is important in designing the protocol is associated with the node selection algorithm based on residual energy.

5. Related work on power-aware routing protocol

   In recent years, there has been considerable interest in energy/power aware routing to extend the lifetime of networks. These protocols usually measure the residual energy (remaining battery life), power consumption, power conservation and value threshold of a node [1].

   At the network layer, routing algorithms must select the best path to minimize the total power needed to route packets on the network and maximize the lifetime of all nodes. Here we will discuss some power efficient route selection schemes to achieve one or both of these goals.

   Power aware routing schemes make routing decisions to optimize performance of power or energy related evaluation metrics. The route selections are made solely with regards to performance requirement policies, and the independent of the underlying ad-hoc routing protocols deployed. Therefore, the power- aware routing schemes are transferable from one underlying ad-hoc routing protocol to another, while the observed relative merits and drawbacks remain valid.

   Several works of Ad hoc networs have been done by different developers around the world to obtain a reasonable and reliable technology in order to be accepted as an alternative medium compared to the existing wired network communication. These developers have focused on many angles such as security, connectivity, as well as the overall reliability of the ad hoc wireless technology.

   However, after several decades, many wireless routing protocols have been developed by different developers, or similar. The focus is on the connectivity portion of the Mobile Ad hoc Network. More specifically, energy/power aware on multipath routing protocols which is one the most prominent of ad hoc multipath protocols is focused. Since, the power of each node in the network is limited, energy remaining, conservation, and consumption is very important. To maximize the lifetime of ad hoc networks, a lot of routing protocols have been proposed.

   Some researchers focus exclusively on energy based node selection in route discovery. Several route protocols have been proposed since the last decade. However, now it is thought that the energy in the node is a significant problem in maximizing the network lifetime. Therefore, a few protocols have been proposed such as Distance-based Energy Aware Routing Wireless Sensor Network (DEAR) [5], Maximum Available Power (MAP) [6].

   Distance-based Energy Aware Routing (DEAR) [5] is a routing algorithm that considers both route setup

   and route maintenance. During the route setup phase, the algorithm first computes the distance between the source and sink nodes ( dn ). If (dn 100), a direct transmission is used, otherwise multi-hop routing will be selected. This algorithm can also determine the number of nodes to function as relay nodes, and the last node in the sequence closest to the sink. This algorithm assumes that high transmission power will drain a significant amount of energy from the nodes. That is, attempting to transmit over long distance consumes more energy compared to low power multi- hop transmission covering the same distance. The downside of this algorithm is that it increases the traffic at intermediate nodes unnecessarily. Due to the increased traffic carried by the node closest to the sink, it will drain out faster than the nodes that are away from the sink. Also DEAR does not measure or base it decision on the available residual energy of a selected node. This may result in an intermediate node becoming totally drained of its energy during transmission interrupting the communication.

   The author in [7] used a short range and non- distance communication between the sensor nodes because of the power transmission is required to give as shown Figure 1. Suppose that node u has to send a packet to node v, which is at distance d. Since node v is within us transmitting range at maximum power, direct communication between u and v is possible. At the same time, there is a node w in the region C circumscribed by the circle of diameter d that intersects both u and v. Let (a,b) be the distance between nodes a and b, respectively. Since (u,w) = d1 < d and (v,w)

   = d2 < d, sending the packet using w as a relay is also possible. However, the author did not take into account the case if node w is outside of C and if node w is not taken as a relay node, u will have direct transmission with v, which will use high energy transmission but with limited distance.

   The author in [8] proposed the Distance-Based Energy Efficient sensor Placement (DBEEP) for lifetime maximization, which jointly optimize the load balance, communication range, and network size in a time-driven linear WSN. DBEEP identifies the traffic load balancing as a critical issue that must be addressed at each node in a balanced traffic flow. This is important since the load balancing on a particular node can increase the network lifetime.

   Figure1. Case for Multi-hop Communication [7]

   The DBEEP comes with an energy model that assumes those nodes, which only relay data to the next node in the direction of the radius is lost. In this model, the configuration refers to the arrangement of those related nodes that are deployed along the radius. If the adjacent node have d1>d2>dn, the connected coverage of the inside nodes will be ensured. Similarly, in [8], the author described the control of energy consumption can be done by controlling the optimum router location, identifying the number of nodes involved, and taking into account the communication costs and the shortest route.

   The literature investigated shows that the Energy- Awareness technique has helped to improve the network connection lifetime. However, the proposed techniques have failed to focus on the energy possessed by individual nodes. By only focusing on the energy consumption, it does not reflect the accurate value of the node capacity.

6. Probability based method for node selection

   The proposed probability based node selection method considers a new parameter known as the energy distance factor. This factor helps to select the best next hop node for optimizing the energy efficiency of the network. The scheme also considers the residual energy of the nodes as a fraction rather than the absolute energy levels. Based on this scheme of selecting nodes with sufficient residual energy, an energy aware routing protocol for MANETs is proposed in this paper. The aim of this scheme is to improve the performance of the path lifetime by selecting the best nodes along the path from the source to destination.

   It is common for each node in a network to have a different energy level. Hence it is important to select the best intermediate node in terms of residual energy.

   If the energy in a node runs out during the transmission of data, it will force a new route discovery process interrupting the data transmission. Route discovery is costly in terms of both transmission delay and energy consumption. During the route discovery, multiple nodes will have to be contacted for the purpose of identifying and establishing the route again. This would consume more energy than that required for transmitting data.

   The nodes between the source and destination are divided into tiers as shown in Figure 2. The tier arrangement is as follows; every node that can be reached directly or by one hop from the source is considered a Tier 1 node, Tier 2 nodes can be reached with only two hops. Similarly, Tier 3 nodes need three hops from the source and so on. Figure 3 shows the distribution of nodes between the source and destination. Depending on the availability of nodes, node distribution can be symmetrical by the straight line connecting the source and destination nodes. The

   Figure 3: Arbitrary Placement of Mobile Intermediate Nodes

   If the energy level and the distance of the node i are given by ei and di respectively.

   The energy-distance factor (i) is computed. Figure 4 shows the representative block diagram model.

   straight line path between the source and destination is the most preferable as it would create the shortest possible path consuming the lowest energy.

   Input

   output

   Figure 4: Representative Block Diagram of the model

   The energy-distance factor (i) is computed as follows:

   energy-distance product of node i (mi)= ei di (1)

   energy-distance factor of node i (i) = eidi (2)

   n

   i =1

   ei di

   Where, n number of nodes in the Tier 1

   Figure 2: Node with energy reachable zone

   MATHEMATICAL FORMULATION

   Figure 2 shows an arbitrary arrangement of nodes in a given situation. The placements of these nodes are arbitrary in the sense that there is no coordination between the nodes either in their location or the direction of their movement. Nodes S, D and i represent source, destination and any arbitrary node in tier 1 respectively.

   Properties of Energy-Distance Factor

   1. lies between 0 and 1 for all

      Proof:

      Consider the extreme case of no other nodes in the vicinity of the source node. Then ei = .

      Thus i = 0

      The other extreme case is only one node in the vicinity of the source node with energy level e and at a distance d.

      Energy-distance product m = ed

      Energy-distance factor = ed

      ed

      = ed = 1

      ed

      For all other cases where there are more than one node in the vicinity of the source.

      Energy-distance product of node i

      mi = eidi < eidi

      , = , + 2 . + . . 2 , < 0

      4

      =

      2 . + . . , 0

      (5)

      Hence, Energy-distance factor of node i

      = ei di < 1

      0

      =

      i

      Thus for all cases,

      eidi

      Eelec : energy dissipation to run the radio device

      : free space model of transmitter

      Energy-distance product of node i is 0 i 1

   2. Sum of all individual values is equal to 1 ( i

      =1)

      Proof:

      Consider that there are n nodes in the tier 1 of source node S.

      amplifier

      : multi-path model of transmitter amplifier

      l : data length

      do : distance threshold

      Hence, when selecting an intermediate node, it is necessary to consider both free space and multipath transmissions.

      Let

      =1

      = 11 + 22 + . . + =

7. Simulation

   =

   (3)

   =1

   The energy behavior of the intermediate nodes was investigated using simulations. A simulation

   =

   environment was setup using GNU Octave 3.2.4

   =1

   software. Figure 5 and 6 shows the residual energy of the intermediate nodes after transmitting a packet of

   = 11 + 22 + . +

   unit size. The experiment has been setup with three intermediate nodes between the source and the destination nodes located at different distances but

   = 11 + 22 + +

   =

   = 1

   (4)

   having the same energy levels. Locating the nodes at different distances create different energy-distance factors for the nodes though they possess the same level of energy. Residual energy has been computed by dividing the energy consumed by the initial energy using Formula (6) and the angle of deviation is the deviation of the intermediate node from the line connecting the source and destination nodes.

   Thus, i behave like a probability

   = =

   (6)

   Since i behaves like a probability and identifies the node with the highest energy distance product, it may

   be used to select the next hop node for forwarding the packet towards the destination. The node possessing the largest value may be preferable compared to the other nodes as the next hop in the direction of the destination. Hence, when selecting an intermediate node, it is necessary to consider both free space and multipath transmissions.

   Energy Behavior of the Intermediate Node

   The energy required to forward a packet of data to the next node is given by [5]:

   Where ER residual energy

   EI initial energy

   EC energy consumed

   EL energy left

   Figure 5: Residual Energy in the Intermediate Node Free Space Transmission

   Figure 6: Residual Energy in the Intermediate Node Multi Path Transmission

   The results shown in Figures 5, and, 6 for both cases, the node with the largest provides the highest residual energy meaning that it has more energy left after the transmission of a data packet. This information is very important for selecting the intermediate node that could provide a stable route in terms of node lifetime. If a node with low residual energy was chosen for transmission, it would not have sufficient energy left for future transmission forcing the nodes to rearrange the routes through other nodes.

   Figure 7: Residual Energy in the Intermediate Node

   Narrower Angle of Deviation

   Figure 7 shows the same information but confined to a narrow angle of deviation. Figure 7 has been plotted specially to clarify the confusion created in Figures 5 and 6 near the origin (0o). From Figure 7, it can be clearly seen that the sharp rise in the residual energy is due to the data point concentrating near 0o only and apart from that it clearly follows the general trend. From these figures, it can be seen that the residual energy increases as the angle of deviation reduces towards origin. This is due to the fact that as the angle of deviation reduces so does the distance between the intermediate node and the destination node.

   Figure 8: Residual Energy in the Intermediate Node Multi Path Transmission

   Figures 8 show the results of the experiment that has been set up using intermediate nodes with different initial energy levels but located at the same distance. Figures 8 show that the intermediate node with the largest has the highest residual energy level compared to the other nodes. This result is similar to the results shown in Figures 5, and 6. In both cases, the node with the largest provides the highest residual energy meaning that it has more energy left after the transmission of a data packet. This information is very important for selecting the intermediate node that could provide a stable route in terms of node life time. If a node with low residual energy was chosen for transmission, it would not have sufficient energy left for future transmission forcing the nodes to rearrange the routes through other nodes. Hence, it can be concluded that the node with the largest energy-distance factor () provides the best intermediate node for the transmission of data towards the destination. This algorithm has shown that the proposed model achieved a good selection based on the residual energy at each node.

8. Conclusion

   The concise discussion in this paper shows that, despite the large efforts of the MANET research community and the rapid progress made during the last years, many issues that affect the energy at the node still has space improvements, particularly involving the routing protocol. The algorithm of nodes selection based on residual energy is the one of the essential to improve the lifetime of network connection by considering the individual energy node. Residual energy level at the node and the distance factor can be used to determine the probability of intermediate node to be select as relay node to destination. This algorithm can prevent the early failure of a node and reflected to reliability of route path. The node with the largest provides the highest residual energy meaning that it has more energy left after the transmission of a data packet. This will extend the route path connection in the entire network path.

9. References

1. Kun W, Yin-Long X, Guo-Liang C, and Ya-Feng W, "Power-aware on-demand routing protocol for MANET," in International Conference on Distributed Computing Systems Workshops, 2004, pp. 723 – 728.

2. Adibi S. S. and Erfani, "A multipath routing survey for mobile ad-hoc networks," in Conference on Consumer Communications and Networking,(CCNC 2006), 2006, pp. 984 – 988.

3. Hang Shen, Guangwei Bai Junyuan Wang and Jinjing Tao, "A power-aware multipath routing protocol for IEEE802.11e wireless ad hoc networks," in International Conference on Communications and Networking,(ChinaCom 2008)., Hangzhou, 2008, pp. 849

   – 853.

4. P. Murali, K. Rakesh, C. Hota, and A. Yla-Jaaski, "Energy-aware routing in Mobile Ad-Hoc Networks," Wireless Days, 2008. WD '08. 1st IFIP, p. 1, 10 April 2009.

5. Jin Wang, I.J. de Dieu, A. De Leon Diego Jose, Sungyoung Lee, and Young-Koo Lee, "Prolonging the Lifetime of Wireless Sensor Networks via Hotspot Analysis," in International Symposium on Applications and the Internet (SAINT), 2010, pp. 383 – 386.

6. Elshakankiri, MN. Moustafa, Y.H. Dakroury, and This, "Energy Efficient Routing protocol For Wireless Sensor Networks," in International Conference on Intelligent Sensors, Sensor Networks and Information Processing,(ISSNIP 2008)., 2009, pp. 393 – 398.

7. M.M.A. Azim, "MAP: Energy Efficient Routing Protocol for Wireless Sensor Networks," in Proceedings of the 4th International Conference on Ubiquitous Information Technologies & Applications, ICUT,, 2009, pp. 1 – 12.

8. Ren L, Guo Z, and Ma R, "Distance-based energy efficient placement in wireless sensor networks," in

   Conference on Industrial Electronics and Applications,(ICIEA 2008)., 2008, pp. 2031 – 2035.

9. Shi Y, Jia F, and Hai-Tao Y, "An improved router placement algorithm based on energy efficient strategy for wireless networks," in International Colloquium on Computing, Communication, Control, and Management, (CCCM 2009)., 2009, pp. 421 – 423.

Author Profiles

Jailani Kadir is a Senior Lecturer attached to the Department of Electrical Engineering, Polytechnic of Ministry of Higher Education Malaysia. He is currently pursuing his PhD on energy aware routing in MANET attached to the InterNetWorks Research Group of the Universiti Utara Malaysia. His research interests include Mobile Ad hoc networks and

routing protocol. Email: jailani@internetworks.my

Dr. Osman Ghazali is an Associate Professor and the Head of the Computer Science Department of the School of Computing, College of Arts and Sciences at the Universiti Utara Malaysia. He was formerly the technical chair of the University Teaching Learning Center (UTLC) of the Universiti Utara Malaysia. His research interests are in Cloud

Computing, Mobile Ad-hoc Networks and Layered Multicast Protocols. Email: osman@uum.edu.my

Dr. Suhaidi Hassan is an Associate Professor and the Assistant Vice Chancellor of the College of Arts and Sciences of the Universiti Utara Malaysia. He is a senior member of the IEEE and the team leader of the InterNetWorks Research Group. His research interests are in Computer and Communications Networks, Information Security and Distributed Systems.

Email: suhaidi@uum.edu.my