Docshare

Published on April 2017 | Categories: Documents | Downloads: 73 | Comments: 0 | Views: 1078
of 7
Download PDF   Embed   Report

Comments

Content

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

An Improvement of Link Failure Maintenance in AdHoc Wireless Network
Sayid Mohamed Abdule InterNetWorks Research Group UUM College of Arts and Sciences University Utara Malaysia 06010 UUM Sintok, Malaysia [email protected] Suhaidi Hassan InterNetWorks Research Group UUM College of Arts and Sciences University Utara Malaysia 06010 UUM Sintok, Malaysia Email: [email protected] Mohammed M. Kadhum InterNetWorks Research Group UUM College of Arts and Sciences University Utara Malaysia 06010 UUM Sintok, Malaysia Email: [email protected]

Abstract— In mobile ad-hoc wireless network, the link failure is a major challenge. It causes a reduction in performance and efficiency of network resources. This paper presents an enhancement to AODV-DFRP protocol. This developed protocol utilizes the link state prediction method to avoid a link failure in a different way from the existing solutions. The paper focuses only the link failure caused by the nodes mobility, which can be avoided if the routing protocol responses quickly to the network topology change. In this paper, we propose a Local Route Request (LRREQ) mechanism which is expected to show better performance than Local Repair method that is used in standard AODV. (Abstract) Keyword: Ad-hoc; AODV;

request (RREQ) packet to its neighbors, which forwards the request to its neighbors until reaches to the desired destinationnode or reaches intermediate node which has information about the route to the destination-node [5]. During the route discovery processing, each intermediate node recodes its own sequence number (called broadcast ID). This broadcast ID is incremented for every RREQ that the node initiates, and also records the nodes IP address (source and destination IP addresses). Intermediate nodes can reply the RREQ, in case they have a route to the desired destination-node, only if the destination sequence number is greater than or equal to that contained in the RREQ [6]. In addition, in forwarding process of the RREQ, the intermediate node records the address of the neighbor from which the first copy of RREQ broadcasted is received, to avoid receiving several copies of same RREQ and to avoid looping problem as well. In case of one of the intermediate nodes receives copies of same RREQ, these packets are discarded. Upon receiving the RREQ by the destination-node or intermediate node with recent route to destination, it responds by unicasting a route replay (RREP) packet back to the neighbors that received the first RREQ from [7]. In the presence of Link Failure in AODV, when an intermediate node discovers a link failure in active route, it broadcasts a route error (RERR) packet to inform the source node. Then, the source node will re-initiate a route discovery process again if necessary [8]. One major drawback of AODV protocol is the source route re-initiating upon a link failure; which is the main point that our paper focuses on. In this paper, we come up with a mechanism that avoids the route rediscovery by the source upon link failure and, at the same time, solves the link failure before the current route becomes completely disconnected. Many ad-hoc routing protocols have been developed, implemented, and they are categorized into different classes. The common routing protocols used in mobile ad-hoc networks (MANETs) are AODV and Dynamic Source Routing (DSR) [9]. These two on-demand ad-hoc network routing protocols are the most widely studied. Subsequently, numerous protocols are being developed or modified which are both proactive and reactive routing protocols, such as Dynamic DestinationSequenced Distance-Vector routing (DSDV), Optimized Link

I.

INTRODUCTION

Mobile ad-hoc Network (MANET) is one of the most focused research areas in the field of wireless networks as well as mobile communication for the last decade [1] [2]. Ad-hoc network consists of nodes communicating one another with portable radios. In ad-hoc mobile networks, routes are mainly multi-hop because of the limited broadcasting propagation range and frequently, and unpredictably, topology changes, as each network node moves randomly. Therefore, the routing protocol is an essence task as it transferring packets form source node to destination. In other words, it can be described as the process of path finding to reach the desired destination. Finding a new path in ad-hoc network has become a hot research issue. In MANET communication, every node in the network acts as a router as it forwards packet from one node to another. Many routing protocols have been developed for mobile adhoc wireless network. Ad-hoc on-demand distance vector (AODV) is one these protocols which have been used widely. AODV is a reactive routing protocol of mobile ad-hoc network [3] [4]. When a host or node wants to send a message to destination-node and does not have a valid route to that destination-node, it initiates a route discovery process in order to find out the destination node. Then, it broadcasts a route

182

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

State Routing (OLSR), Topology Broadcast Based on Reverse Path Forwarding (TBRPF), Signal Stability based Adaptive routing (SSA), and mixed routing protocols such as the Zone Routing Protocol (ZRP), and many others [10]. The goal of this paper is to propose a very useful mechanism to improve AODV-DFRP protocol “in press” [11] and enhance overall adhoc wireless network. II. RELATED WORK

to find a fresh route to the destination. This mechanism has a common weakness as many other mechanisms did, namely sending an unnecessary warning messages propagating back to the source node which again increases the traffic in the network. III. THE PROPOSED APPROACH

On mobile ad–hoc wireless networks, the route disconnection has a significant negative impact on packet delivery. The common drawbacks and main consequences of route failures are packet dropping, end-to-end delay, and minimum throughput. These result in overall network inefficiencies. In addition, the interval time for link break detection and construction time of alternative path can be high. Therefore, many link predication studies have been proposed, recently, which focus on improving route repair in advance. In [12], a Predictive Preemptive approach has been proposed to route maintenance and to avoid link breakage. The mechanism is initiated when a link is about to be broken instead of waiting for the break to happen. This approach used the Lagrange interpolation mathematical model in order to estimate whether an active route to a neighboring node will fail. When link failure is expected between a node and an upstream neighbor, the upstream neighbor itself attempts, first, to find a route to the destination. If such route is not found within a discovery period, a link failure warning is propagated via upstream nodes to sources that use this link. Source nodes invoke the route discovery mechanism if they need a route to the destination. This approach has two drawbacks: (i) if the problem is happened at the upstream node and not downstream, it is going to take quite a long process to divert route. (ii) The mechanism shows that the unnecessary warning message is still sending to the source after a certain period of time which increases the traffic in the network. In [13], a new flooding mechanism is suggested to control route paths. The main point of the proposed scheme is to track the destination’s location based on the beacon messages of the main route nodes by directional forwarding algorithm. In other words, each node recognizes its location through Global Positioning Systems (GPS) for a one-hop neighbor node, which is at a distance of one hop from the main route, recognizes the location of the main route node through a beacon message. GPS has some issues; such as the cost associated with their use and that they may not work properly because of fading. In addition, other problems with this mechanism could be that the need for synchronization between the internal clocks of nodes [14]. [15] introduces the Packet Received Time (PRT) to predict the link status in order to avoid link breakdown on an active route beforehand. This approach used power measurement of received packets to predict the topological change. This mechanism works as follows; if current signal of the received packet is greater than the previous one, it indicates the link is stable and do not need prediction algorithm. But if it is weaker than the previous received packet’s signal power, then prediction algorithm send RERR upstream to locally maintain the route, or to the source (initial node) to establish new RREQ

Our approach concerns an avoidance of link breakage before it becomes completely disconnected. The main goal of the proposed mechanism is to avoid sending an unnecessary warning message upon link failure. In addition, it is an improvement of AODV-DFRP protocol proposed by Sayid “in press” [16]. However, the avoidance of the reverse route to the sender (source) is the similar objectives for both LRREQ and AODV-DFRP protocol upon link failure. This paper proposes two mechanisms to improve the DFRP protocol. They are as follows.   Local Route Request (LRREQ) Upstream Notification (UN)

Before we present the new proposed mechanisms, we provide a brief introduction about how the DFRP protocol works upon a link failure. DFRP protocol uses two mechanisms in order to predict the link breakage and take action before it happens. For prediction, it utilizes the link state prediction method to collect the current link signal strength status in order to detect link breakage. For local or neighbors signal status, it utilizes IEEE 802.11 of wireless standards for beacon frames to find the node that has a stronger signal compare to the current connection signal strength among neighbors. Once one of those neighbors replies with positive response and have both stronger signal and route to the destination, the current-node will divert the route into that node. The weakness of DFRP protocol is, if none of neighbors has stronger signal strength than the current route or it does not have a route to the destination at all, then the protocol will face a problem in order to process the data forwarding. Our new mechanism, LRREQ, uses the link state prediction method, as well, for predicating an active link. In addition, a LRREQ with beacon mechanism will use one hop neighbors to collect their signal status. LRREQ mechanism uses one hop range. After the link state predication algorithm informs that the link between A and B will be broken soon (Figure 1), node A circulates a local route request to neighbors to check signal status and whether there is a route to the destination as shown in Figure 2.

183

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

S

Se n d

er

AODV traditional mechanism. In this respect, node A circulates a Local Route Request (LRREQ) among its neighbors, except the node that node A is receiving from (it does NOT circulate to upstream node), to find out if there is a node that has a stronger signal than downstream node (in this case, the downstream node is “B”) and, at the same time, has a route to the destination (Figure 2).
A B

A. Upstream Notification (UN) If current node (in this case, node “A”) could not receive a positive response from its neighbors (because no one has a route to the desired destination or maybe they do not have a stronger signal than the current connection), the current node (A) will send a notification to previous node (one hop to upstream) indicating the link will be broken soon.
R

Receiver
Prediction model notified that A-B Link is going to be broken soon.

Figure 1. Link A-B is to be broken soon

S

Se n d

er

Thus, when this node (the upstream node) receives such notification from the next hop (downstream), it circulates a Local Route Request into its neighbors except the upstream one and so on. This procedure is presented in Figure 3. The upstream notification continues until a new route to the desired destination is found.
S
Se n d er

g atin S cu l Cir RQE R L
UP

UP

g atin S cu l Cir RQE LR
A

N ifi ot ca tio n
A

No rou te

No rou te

B

B

“Node UP ” circulate a Request to adjacent, if there is a strong signal than “B”

R
Receiver

“A” circulate a Request to adjacent, if there is a strong signal than “B” Upstream node:

R
Receiver

UP

Upstream node to node A: But now the UP is the current node which circulates the Request after UP received NOTIFICATION sent by node A. Node UP’s neighbors Notification: the link soon broken

UP

Where node A receiving data.

Node A’s neighbors
A

Current node: where the information about the link will be broken soon has been notified by link state prediction method Node B is the node that causes the link failure

Node A’s neighbors which did not success the Route to the Destination

Local Route Request & Signal strength among neighbors Indicates there is No Route to the destination. Transmission range of node A

S
R

Source (sender): the node that initiated a connection to R Destination node

Figure 3. Figure 2. Node A circulates a Request to adjacent

sending a upstream notification

IIII.

LOCAL ROUTE REQUEST (LRREQ)

LRREQ comes up with a very useful mechanism on link failure route maintenance. The steps of this mechanism are shown in the through Figures 1-5. LRREQ mechanism is used when the link state prediction model notifies that the link between two intermediate nodes on an active link will be broken soon. This means that, when the A-B link is going be collapsed soon, node A takes an action to sort out the matter, instead of sending warning message back to the sender as in

Figure 3 shows that the node A is failed to sort out the link redirection after the link state prediction informed that the A-B link will not be continued. As mentioned earlier, in LRREQ mechanism, node A will circulates two inquires (for the purpose of finding a stronger signal and a route to destination) to neighbors simultaneously and if one of these inquires not fulfilled, the process will not continue by send a notification to the previous node to indicate that the existing link will be disconnected. This message also includes the status of the signal between nodes A and B. So when the previous node (in this case is node-UP) receives such notification, it will circulate

184

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

LRREQ to its neighbors, as node-A did. If node-UP not succeed to sort out, it continues sending the notification to upstream nodes until a new route to the destination is discovered.

They are:  Distance  Time

S

Se n d

er

UP

C:

Re

n sp o

se

In the distance method, the received signal power solely depends on its distance to the transmitter. In this method we assume that the speed, direction, and transmission range are constant. Therefore, the speeds and directions for node A and node B do not change from to t, where is the start point. It can calculate the distance d from A to B at time t .As stated in [17] and [18]; the distance can be computed as follows.
tio n
A

N ifi ot ca

C

(1)
B

B

l

d
m

Node-C: Response: which means it has both signal stronger And a route to the destination.

R
Receiver

t

A

Figure 4. Node C responses to indicate that it has both a stronger signal and route to the destination

If a neighbor node, for example C in Figure 4, has stronger signal than node A to node B, node-UP has to divert the route through the node C (Figure 5), because A-B link is soon to be broken (because node B is moving beyond the coverage range of node A). Intuitively, as the distance between two nodes is greater than the radius of their transmission range, they will not be able to communicate each other. Figure 5 shows that a new route through node C is constructed. The data flow through node A to node B will continue via the new constructed path without any loss.
S
Se n d er

From this simple calculation, we can predict the time t when mobile node A and B are going to be disconnected. Thus, this method is solely depends on the distance between nodes.

The time method, having knowledge of the distance d, it can predict the time t when node A and node B are going to be disconnected. We can calculate the distance d from A to B at time t as mentioned earlier. Also we can calculate the remaining time that the link will stay connected with known transmission range r. For example, A and B are within the transmission range r at ( , ) and ( , ) moves with speed , at direction , . ( and are in the range of 0 to 2 ), respectively. So the remaining time of link connection is: ,

UP

(2)
,

C
A B

Where: a d VI.

,b .

ONE-HOP-NEIGHBOR SIGNAL MONITOR

R
Receiver
New route is created through node-C along to the destination

Figure 5. Link Divert Through Node C

The one hop neighboring signal status is also important to monitor. The circulation of LRREQ among neighbors upon the prediction of a link failure derives creating an array for each node to keep the signal information, called “signal-status array”. This array holds three packets for beacon signal strength and their reception time. This is done by Lagrange Interpolation method which has the following general definition.
(3)

IVI.

PREDICTION OF AN ACTIVE ROUTE

Basically there are two methods, to predict the mobile nodes connectivity.

185

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

+ +

B. Flowchart of the New Mechanism
Start

The strength powers and time intervals are . In this respect, if the signal threshold less than the minimum requirement of signal power or there is no route to the desired destination, a warning message is sent to the upstream node. This is shown in the following pseudo code and flowchart. A. Pseudo Code of the New Mechanism
// /* // = Threshold or required signal power/* // one-hop-S-Pw = one hop neighbors signal power /* // signal-status-array[3]; = table contains signal status/* Predict() // execute prediction in every 5 ms {if ( ) than S-LRREQ(signal-power, dest-Route) /* check one-hopneighbor, if one of //them got stronger signal than current, plus destination //route as well. */ }; // One-hop-Response Response() // one-hop-neighbors response signal-status-array[3]; // table contains signal //status {if (one-hop-S-Pw > S-LRREQ(signal-power, destRoute)) //* comparing signal power of the one-hop //neighbor with the active route signal power.*/ Divert-Data (new-path) // Divert data into the new path Else Send-UN(signal-power, dest-Route) //* send notification to upstream node*/ };

Predict();

1. Predict(): Call predication function 2. No Check if link being broken soon 3. S_ LRREQ(); If yes, than send an inquiry

Yes S_ LRREQ();

Node A One-hop-S-P > S_LRREQ() ?

No

UN

Yes Yes Forward data through the new path
Upstream-node One-hop-S-P > S_LRREQ() ?

No

4. Node A/UN Finally, if all requirements are not fulfilled, than sends UN.

End

Figure 7. Flowchart

CONCLUSION In this paper, we propose a new mechanism to improve adhoc wireless network performance and to overcome link failure problem. The new mechanism detects link failure before it completely occurs, finds a new route, then divert the data through the new route without loss. This mechanism is supposed to eliminate the route re-establishing by the source upon link failure. In addition, it improves the limitation of DFRP protocol upon receiving a negative response from neighbors (neither signal stronger nor route to the destination). The proposed mechanism is expected to improve the network performance significantly, reduce network overhead, decreases the packet loss, reduce end-to-end packet delays, increase the throughput, utilize the network resources efficiently, and improve packet delivery ratio.

Figure 6. Pseudo Code

186

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

REFERENCES
[1] Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET) Working Group Charter, Chaired by Joseph Macker and M. Scott Corson, http: / /www. ietf.org/html. charters/manetcharter. html. J. Jubin and J.D. Tomow, “The DARPA Packet Radio Network Protocols.” Proceedings ofthe IEEE, vol. 75, no. 1, pp. 21-32 January 1987. C. E. Perkins and E. M. Royer, “The Ad Hoc On-DemandDistance Vector Protocol”, Ad hoc Networking, Addison-Wesley, pp. 173219, 2000. C. E. Perkins, E. M. Belding-Royer and S. Das, “Ad Hoc OnDemand Distance Vector Routing”, IETF RFC3561, July 2003. [5] Dube R. “Signal stability based adaptive routing for ad hoc mobile networks”, IEEE Computer Community, 1997. Zhijiang C., Georgi G., and Stamatis V. “Routing Protocols for Mobile Adhoc Networks Current Development and Evaluation”, Delft University of Technology. Netherlands, 2006. He, D.; Jiang, S. and Rao, J.,”A Link Availability Prediction Model for Wireless Ad Hoc Networks”, Proceedings of the International Workshop on Wireless Networks and Mobile Computing”, Taipei, Taiwan, pages D7-D11, April 2000. Zhijiang C., Georgi G., and Stamatis V. “Routing Protocols for Mobile Adhoc Networks Current Development and Evaluation”, Delft University of Technology, Netherlands, 2006. Awos Khazal Ali. “An Alternative Routing Mechanisms For Mobile Ad-Hoc Networks”, Faculty of Computer Science & Information Systems Universiti Teknologi Malaysia, 2008. Ammar Zahary and Aladdin Ayesh , ”Analytical Study to Detect Threshold Number of Efficient Routes in Multipath AODV Extensions” Faculty of Computing Sciences and Engineering De Montfort University Leicester, LE1 9BH, UK, 2007. Sayid Mohamed Abdule and Suhaidi Hassan, “Divert Failure Route Protocol Based On AODV”, proceedings International Conference on Network Applications, Protocols and Services (NetApPS 2010), Universiti Utara Malaysia, 2010. Hacene et al, “predictive preemptive ad hoc on-demand distance vector routing”, Malaysian Journal of Computer Science, Vol. 19(2), 2006. Byung-Seok Kang et al, “Effective Route Maintenance and Restoration Schemes in Mobile Ad Hoc Networks”, Department of Computer Science, Korea Advanced Institute of Science and Technology (KAIST),2010. Sofiane Boukli Hacene et al, “Predictive Preemptive Ad Hoc OnDemand Distance Vector Routing”, Malaysian Journal of Computer Science, Vol. 19(2), 2006.

[2]

[3]

[4] [5] [6]

[7]

[8]

[9]

[10]

[11]

Sayid Mohamed Abdule, received his BSc degree in Computer Science from Agder University, Norway.and, his M.Sc degree in Satellite Communication focusing Quality of Service of VOIP over Satellite from the University Sains Malaysia (School of Computer Science), MALAYSIA. Sayid currently attached to the InterNetWorks Research Group at the UUM College of Arts and Sciences as a doctoral researcher. He is currently pursuing his PhD research in Ad-hoc Mobile networking. His current research interest is on Ad-hoc mobile network routing protocol.

[12]

[13]

[14]

[15] Naif Alsharabi et al, “Avoid link Breakage in On-Demand Ad-hoc Network Using Packet’s Received Time Prediction”, College of Computer & Communication Hunan University – changSha , proceedings 19th European Conference on Modeling and Simulation Yuri Merkuryev, Richard Zobel, Eugene Kerckhoffs, 2005. [16] Sayid Mohamed Abdule and Suhaidi Hassan, “Divert Failure Route Protocol Based On AODV”, proceedings International Conference on Network Applications, Protocols and Services (NetApPS 2010), Universiti Utara Malaysia, 2010. [17] He Dajing, Jiang Shengming and Rao Jianqiang, “A Link Availability Prediction Model for Wireless Ad Hoc Networks”, Proceedings of the International Workshop on Wireless Networks and Mobile Computing, pp. D7-D11, Taipei, Taiwan, April 2000. [18] Rappaport, T. S., .Wireless Communications: Principles and Practice (2nd 107 Edition)., Prentice Hall, ISBN: 0130422320, 2002.

AUTHORS PROFILE

Mohammed M. Kadhum, Ph.D. is an assistant professor in the Graduate Department of Computer Science, Universiti Utara Malaysia (UUM) and is currently attached to the InterNetWorks Research Group at the UUM College of Arts and Sciences as a research advisor. He had completed his PhD research in computer networking at Universiti Utara Malaysia (UUM). His research interest is on Internet Congestion and QoS. He has been awarded with several medals for his outstanding research projects. His professional activity includes being positioned as Technical Program Chair for NetApps2008 and NetApps2010, a technical committee member for various well known journal and international conferences, a speaker for conferences, and a member of several science and technology societies. To date, he has published a number of papers including on well-known and influential international journals.

187

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

(IJCSIS) International Journal of Computer Science and Information Security, Vol. 8, No. 5, August 2010

Associate Professor Dr. Suhaidi Hassan, is currently the Assistant Vice Chancellor of the College of Arts and Sciences, Universiti Utara Malaysia (UUM). He is an associate professor in Computer Systems and Communication Networks and the former Dean of the Faculty of Information Technology, Universiti Utara Malaysia. Dr. Suhaidi Hassan received his BSc degree in Computer Science from Binghamton University, New York (USA) and his MS degree in Information Science (concentration in Telecommunications and Networks) from the University of Pittsburgh, Pennsylvania (USA). He received his PhD degree in Computing (focussing in Networks Performance Engineering) from the University of Leeds in the United Kingdom. In 2006, he established the ITU-UUM Asia Pacific Centre of Excellence (ASP CoE) for Rural ICT Development, a human resource development initiative of the Geneva-based International Telecommunication Union (ITU) which serves as the focal point for all rural ICT development initiatives across Asia Pacific region by providing executive training programs, knowledge repositories, R&D and consultancy activities. Dr. Suhaidi Hassan is a senior member of the Institute of Electrical and Electronic Engineers (IEEE) in which he actively involved in both the IEEE Communications and IEEE Computer societies. He has served as the Vice Chair (20032007) of the IEEE Malaysia Computer Society. He also serves as a technical committee for the Malaysian Research and Educational Network (MYREN) and as a Council Member of the Cisco Malaysia Network Academy.

188

http://sites.google.com/site/ijcsis/ ISSN 1947-5500

Sponsor Documents

Or use your account on DocShare.tips

Hide

Forgot your password?

Or register your new account on DocShare.tips

Hide

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

Close