Journal of Computer Engineering & Information Technology.ISSN : 2324-9307

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.

Research Article, J Comput Eng Inf Technol Vol: 9 Issue: 1

Cooperative Hybrid and Scalable Opportunistic Routing Scheme for Mobile Large-scale Wireless Network

Ali Alshehri*, Hong Huang and Shamsad Parvin

Klipsch School of Electrical and Computer Engineering, New Mexico State University, USA

*Corresponding Author: Ali Alshehri
Klipsch School of Electrical and Computer Engineering, New Mexico State University, USA
E-mail: [email protected]

Received: December 10, 2019 Accepted: January 22, 2020 Published: January 29, 2020

Citation: Alshehri A, Huang H, Parvin S (2020) Cooperative Hybrid and Scalable Opportunistic Routing Scheme for Mobile Large-scale Wireless Network. J Comput Eng Inf Technol 9:1.

Abstract

Recently, as a result of the tremendous increases in large-scale multi-hop wireless network communication applications, network capacity has decreases as the number of nodes increase. The existing routing protocols have significant limitations, such as long delays, network infrastructure requirements, limited traffic pattern, or high technical complexity, and efficient spectrum utilization, in terms of the bandwidth efficiency, cannot solve this capacity problem. For this reason, wireless network capacity scaling is a fundamental issue. In this paper, a novel scalable opportunistic routing scheme for a large-scale multi-hop wireless network, is introduced. This proposal presents novelties with respect to both the candidate selection and coordination mechanisms, which will facilitate the improvement of network scalability as well as supporting multimedia traffic. In this routing scheme, we consider a hybrid network, that consists of directed energy (DE) links and omni-directional (OD) antenna links. To quantitatively select the best potential candidate nodes, the forwarder node relies on a proposed metric termed scalable opportunistic objective function (SOOF) which considers DE link presence, one-hop throughput, node mobility, and expected distance progress toward destination. We compare the performance of the proposed routing scheme with three other relevant protocols: DSDV, AODV, and GOR. For precise analysis, the performance of the routing protocols is evaluated by considering various network metrics. Our simulation result validates our analysis and demonstrates that the proposed routing scheme significantly outperforms the relevant routing protocols.

Keywords: Large scale multi-hop wireless network; Directed energy links; Omni-directional link; Opportunistic network

Introduction

In large-scale wireless networks, nodes are interconnected through mobile multi-hop wireless network. The key features of this wireless architecture are the large number of mobile nodes, the ability to operate in the absence of communication infrastructure, and a highly dynamics environment [1,2]. The applications of this wireless architecture range from civilian applications (example: distributed computing) to disaster relief example: floods, earthquakes), and military application (example: automated battlefield). Human-to-human communication plays a significant role in these applications; therefore, the ability to support multimedia communications is an essential qualification of routing protocols operating in large-scale wireless networks.

Although, the conventional routing protocols that have been designed for mobile ad hoc networks (MANETs) facilitate communication between mobile devices in the absence of an infrastructure, they suffers from frequent intermittent connectivity, long end-to-end latency, and large overhead introduced by routing protocols control messages, which is a stumbling block of network capacity scaling [3]. In addition, Gupta and Kumar [4] have demonstrated that the per-node average throughput of a multihop wireless network of n nodes scale as image and can decrease roughly in proportion to the inverse square root image of the number of nodes in the network. This result has significant implications for designing routing protocols that can scale [2]. These limitations of the conventional routing protocols demand a new and novel communication paradigm for the highly dynamic wireless large-scale network.

Recent years have witnessed increasing interest in utilizing directed energy DE links in MANETs due to the potential bandwidth capacity increases provided by DE links. Most previous research on DE links proposed algorithms to acquire and maintain DE links in dynamic networks [5,6]. However, in this work, we consider a different approach that will allow the utilization of DE links even when they are unreliable and unpredictable under dynamic network conditions. This approach was validated in our prior preliminary work [2], in which we provided a mathematical model that enabled us to prove that network scalability is indeed achievable in large- scale networks by averaging across many random unreliable DE links.

In addition, our approach addresses another challenge in largescale networking: the high cost of distributing network global routing information. Although the capacity of large- scale wireless networks has been studied extensively, little attention has been paid to how practical routing protocols may best be implemented in large-scale wireless networks. It is impossible to ignore network dynamics in large-scale networks: nodes can join, leave, or move, and channels can fade. The network links are particularly volatile when DE links are involved. However, distribution of global routing information incurs high costs. In a network of n nodes, the overhead of a routing protocol, such as proactive routing protocol, scales as n / logn, whereas the total network capacity scales as n / logn [4], which may be overwhelmed by the routing overhead as the number of nodes increases. We demonstrate that our distributed opportunistic routing scheme is independent of network global routing information and rely on the local routing information to make routing decisions using our approach [2].

In this paper, we propose a novel opportunistic routing (OR) scheme that is able to scale through the use of DE links in a hybrid dynamic large-scale multi-hop wireless network. We consider opportunistic routing as an underline communication platform due to its flexibility in adaption to the dynamic behavior of nodes and its ability to reduce the requirements of topology storage. Furthermore, OR exploits the broadcast nature of the wireless medium by taking advantage of the ability of nearest neighbors to overhear a forwarder transmission; thus, the forwarder can recruit multiple one-hop neighbors as potential candidate in local forwarding. The proposed routing scheme implements a prediction-based objective function for opportunistic candidate selection called scalable opportunistic objective function (SOOF) that captures: DE link presence, one-hop throughput, node mobility, and distance progress toward destination.

The proposed hybrid network bears a strong resemblance to the classical small-world-phenomenon [7], which showed that the nodes are connected by a surprisingly small number of hops in a large network with a mixture of short-distance and long-distance links, which mirrors a hybrid network of OD and DE links. Since the capacity of multi-hop wireless networks is limited by the number of hops a packet has to travel to reach its destination [4], a small number of hops translate to high capacity.

In this paper, we make the following contributions:

A novel DE links-aware opportunistic routing protocol that leverages the presence of DE links in the routing paths towards the destination;

A heuristic algorithm for selecting potential OD candidates and assigning relay priority to them based on the SOOF metric value.

A new coordination scheme between DE and OD candidate nodes is developed, for the purpose of determining which candidate will relay the packet to control transmission duplication;

An implementation of the proposed routing scheme in an ns − 3 [8] simulator; and

A performance evaluation of the proposed routing scheme directly compared with three state of the art MANET routing protocols namely destination sequenced distance vector routing (DSDV) [9], ad hoc on-demand distance vector (AODV) [10], and geographic opportunistic routing (GOR) [11].

The remainder of this paper is organized as follows: in Section II we review the related literature, focusing mostly on the opportunistic routing and hybrid DE/OD MANETs. In Section III, we describe the system model and the assumptions. A details description of the proposed scheme and its objective function and features is offered in Section IV. In Section V, the routing scheme implementation is discussed with the simulation setup and performance evaluations. Finally, Section VI concludes the paper.

Related Work

In this section, we present an overview of related work on opportunistic data dissemination schemes for multi-hop wireless networks and hybrid DE/OD MANETs networks.

Opportunistic networks

Opportunistic networks (ORNETs) have emerged as a new communication paradigm for ad hoc networks. The irregularities that are characteristic of wireless networks, such as the frequent intermittent links between nodes, the absence of instantaneous endto- end paths, and communications delays that may be very long, are considered to be norms in ORNETs [12,13]. Examples of ORNETs include delay-tolerant networks [14,15], and packet-switched networks that created out of wireless devices that connecting mobile users with-out relying on any preexisting network infrastructure [16]. The data dissemination schemes in the previously proposed ORNETs can be broadly divided into epidemic and non- epidemic schemes, based on the number of packet copies in each physical transmission. In epidemic schemes, multiple copies of the same packet are generated by each node, while in non-epidemic scheme, a single copy of a packet is sent to single node in every routing step. Examples of non-epidemic schemes include data dissemination schemes based on forwarding probability estimation of neighbors, according to historical data in [17]; location-based schemes, which use neighbors’ locations as a context for selecting the next-hop forwarder (the node that makes the most distance progress toward the destination is selected as the best next- hop node) [18,19]; the mobility-based scheme, which allows nodes to make better forwarding decisions based on forwarding probability estimation of its neighbors by considering the nodes’ regular mobility patterns. Example of epidemic data dissemination schemes includes [20,21]. Vahdat et al. [22] proposed the first epidemic data dissemination scheme, whereby a packet replicates for a sufficient number of times and randomly exchanges to ensure that all network nodes will eventually receive a copy. Spyropoulos et al. [23] proposed a spray-and-wait data dissemination scheme to limit the cost of data replication. Data dissemination schemes based on historic meeting information [24-26] were proposed to allow nodes to make better data replication decisions. Network coding was proposed to improve the efficiency of data dissemination in ORNETs [21].

Hybrid DE/OD manet wireless network

DE links, such as laser communications links or highly directional pencil beam, in some literature is called free space optical (FSO) [27], have some advantages over OD links. DE links have the advantage of higher capacity, long transmission range up to tens of kilometers [5], less interference with transmission signals, and license-freespectrum. However, DE links are highly fragile: they require clear line- of-sight alignment during communication. DE links can be easily disrupted by the effects of nodes mobility, fog, dust, heat, and natural or artificial obstacles [28-30]. There have been several studies that focused on designing and developing routing scheme for utilizing DE in MANETs. In [31] the authors developed a network paradigm that consider delay tolerant networking (DTN) routing concept in MANET, which suites DE links characteristics. The DE links communication duration between any two arbitrary network nodes depend on nodes mobility rate and line-of-sight. The authors assumed that the hybrid DE/OD architecture is employed. Where every network node equipped with two types of antennas, DE and OD. The Global Position Serves (GPS) is assumed to be available to the network nodes. The OD antenna utilized to exchange the network control packets between mobile nodes such as hello packets and location information. The designed DTN approach relay on single-copy routing and the routing decisions made hop-by-hop depend on line-of-sight and the available network information. The authors of [6] developed a hybrid MANET network paradigm, where nodes equipped with DE/OD communication technology. The main motivation for the researchers was to cope with convention MANETs bandwidth constraints. In this research, the OD links are designed to work as a low-bandwidth backup links to the primary DE links. This network system designed for unmanned robot in a disaster relief environment. Additionally, authors proposed DE links acquisition scheme for mobile robots to have ability to pair with each other. The DE links acquisition alignment designed to perform in three phases: alignment based on local sensors where the robots assumed to have each other GPS location information, refinement the line-of-sight considering high camera zoom, and finally precise DE alignment. On the other hand, the authors adopted hierarchical state routing (HSR) algorithm as a routing scheme where the mobile robots are considered as a cluster head to establish hierarchical network architecture.

System Model and Assumption

Network model

We consider a network composed of a large number of mobile nodes Ν Among these mobile nodes, few are equipped with longrange (ΝDE) transmission capabilities, and others use the common short-range (ΝOD). Network nodes are connected by two kinds of links: OD and DE links. OD links have low capacity and are relatively stable (i.e., long lifetime). DE links require line-of-sight, have a high capacity, and are highly dynamic (i.e., short lifetime). Accordingly, OD links are structured in the sense that they only connect nodes in the immediate neighborhood; DE links are random in the sense that they can connect random nodes far away from each other wherever the line-of-sight exists, and weather conditions are good. As a practical example, we may imagine soldiers carrying OD radios and vehicles equipped with both OD and DE radios (Figure 1). The basic approach is to use an opportunistic wireless network with OD links providing relatively stable network infrastructure, upon which the opportunistic usage of DE links makes it possible to improve network scalability.

Figure 1: Hybrid network consisting of DE links (in red) and OD links (in black).

Figure 2 illustrates a sample hybrid network scenario, in which the source node randomly selects a destination node. The routing process from source to destination can be realized in several phases. In the first phase, the current custodian node replicates the packet over the OD links through geo-cast to a set of nodes called candidate set which consists of one-hop neighbors. Then in the second phase, based on a proposed metric, the potential candidate are selected and prioritized. Whenever there is a DE link in the candidate set, it is assigned the highest priority among the candidate nodes to be the next- hop forwarder. When a packet is successfully transmitted over DE links to the remote node of the link, the remote node becomes the new custodian of the packet. The old custodian sends a control message to instruct the candidate nodes to discard the packet. The packet transmission process is repeated until the packet is eventually delivered to its final destination.

Figure 2: Motivation scenario of hybrid network consisting of two DE links (in orange) and OD links (in gray). DE Links enable shortcut paths towards the destination node (D). OD paths can be longer and slower.

In addition, OD nodes can observe the presence of DE nodes within the communication range by exchanging Hello packets. Table 1 illustrates the format of the Hello message used in our routing scheme, which includes the sequence number of the packet, which indicates the freshness of the carried information, the forwarder’s ID, which identifies the node in the network, the forwarder’s position where every node has the ability to access its location information through GPS, velocity, and the essential flag that identifies the DE node. Only DE nodes can adjust the DE flag value and change it to 1. By receiving the DE node Hello message, OD neighbors update their neighbors table and store DE node location information.

Parameter Value
Packet Sequence Number 2 bytes
Originator ID 4 bytes
Originator Position 16 bytes
Originator Velocity 16 bytes
DE Flag 1 byte

Table 1: Hello packet format.

Omni-directional propagation model

We consider the shadowing propagation model to estimate OD link delivery probability, where the received power at a distance d is identified as a random variable due to fading effects, and it can be calculated by the following expression [32]:

image (1)

Pr=is the power of the signal at the receiving antenna at a distance d.

Pt=is the power of the signal at the transmitting antenna. Gt and Gr are the antenna gains in transmitting and receiving, respectively.

L =is a system loss.

λ =is the wavelength of the signal (c/f, with c=3×108 m/s).

β =is the path-loss exponent, and X dB is a Gaussian random variable with zero mean and a standard deviation σ dB . The default shadowing model parameters values are shown in Table 2. In our simulation, we have set the values of these parameters equal to β =2.7 and dB =6 as in [32,33].

Parameter Value
Pt 0.28183815Watt
RXThresh 3.652 × 10−10Watt
Gt, Gr, L 1
f 914MHz

Table 2: Default NS-3 values for the shadowing propagation model.

For a packet to be considered correctly delivered, the power of the signal at the receiving antenna must be greater than or equal to the selected RXThresh. Thus, the link delivery probability at a distance d is calculated as follows [32,33]:

p (d ) = Pr (d ) | dB ≥10log10(RXThresh) (2)

Directed energy propagation model

We consider the well-known DE propagation model [34] to imitate the fading signal characteristics of DE links. Light- emitting diode (LED) intensity follows the Lambertian law, in which the light intensity is proportional to the cosine of the angle of visibility from which it is viewed. Based on Lambertian law, the received signal power PS, at a distance d, and by considering an arbitrary angle α , the LED’s light intensity can be expressed by the following equation:

image (3)

The beam width WB of the DE link transmitter in general at vertical distance d can be defined as the radial distance at which the received signal power is 1/ e2 PS. Accordingly, the divergence angle θ is considered to be a special case of the arbitrary angle α, where the ratio

image (4)

Holds, and thus θ can be calculated by the following expression [5]:

image (5)

DE links performance and propagation are directly affected by atmospheric turbulence (AT ) and geometric distance (AG) between DE transmitter and the corresponding receiver [5], which practically necessitates that the signal power at the receiver must be greater than or equal to the selected threshold. The power loss of DE links due to atmospheric turbulence is given by Bragg’s Law [5,34]:

AT =10log(e-σR) (6)

σ is coefficient of atmospheric attenuation, which includes atmospheric absorption and scattering.

For the wave- lengths of DE links, we considered Mie scattering as in [5], and the path loss is given by this expression [35]:

image (7)

V=is the atmospheric visibility in kilometers.

q=are the scattering distribution size and its value directly depending on the visibility:

image (8)

The geometric attenuation (AG) on the other hand, is a function of the Euclidean distance between DET transmitter, receiver DER, the divergence angle of the transmitter θ , transmitter radius ζ , and the receiver radius ϕ cm [5,34].

image (9)

The Proposed Candidate Selection Algorithm and Coordination Mechanism

The proposed model is an opportunistic routing scheme that adopts some of its features from other routing proto- col architecture namely, throughput efficiency of geographic opportunistic routing [13]. Expected distance progress opportunistic routing [33] is another routing scheme whose metrics we adopted. The proposed routing scheme is designed to work in a variety of mobile wireless networks with or without the presence of DE links. Several configuration parameters of the proposed routing scheme are adjustable so that it is adaptive to different network environments. One of the characteristics of the proposed routing scheme is that the routing decisions depend on the proposed metric value, which simplifies network settingup operations where there is no need for any network layer system management. Consequently, this will alleviate the networks overall end-to-end delay. In this section, we define multiple network metrics in relation to mobile ad hoc networks with the aim of improving online routing decision.

One-hop throughput

To improve routing performance in an opportunistic net- work, the one-hop performance should be maximized along the path.

The throughput can be defined as the maximum number of bits rate successfully transmitted during a given time interval between two network nodes [4,13]. To predict the one-hop throughput, it is necessary to measure the expected transmission time needed to deliver a packet from a forwarder to a Ci(th) forwarding candidate and receive the corresponding acknowledgment (ACK) frame. Accordingly, transmission time is divided into two parts: Channel Contention Time (CCT) and Data Transmission Time (DTT). In contention- based MAC protocols, CCT indicates the waiting time needed before a forwarder acquires the wireless medium to actually transmits a data packet. In addition, CCT may also include the backoff time and Distributed Inter-frame Space (DIFS), while DTT is the total amount of time from the forwarder broadcasts a data packet to the time when the forwarder receives the ACK frame. Thus, we define the total amount of transmission time (TMT) required for a packet, as follow [13,36]:

image (10)

In addition, we integrate numbers of network metrics to maximize the achievable one-hop throughput, and these metrics are:

1) The expected distance progress toward the corresponding destination to minimize hop-counts required to relay the data packet;

2) The link delivery, imageprobability to ensure the transmission reliability for further improvement

of routing performance. Thus, relying on the above analysis, the one-hop throughput can be calculated using the following expression [13]:

image (11)

image is an ordered set of candidate nodes for node S used to reach destination D with priority c1>c2>.......>ci. That is, ci will relay the source packet if none of the higher priority candidates have relayed the transmitted packet.

image Indicates the failure probability of all candidatesimage receiving the source transmitted packet in one transmission.

The expected distance progress toward destination that a candidate ci offers can be calculated by the following equation:

image (12)

Link duration prediction

The relative movement of nodes significantly influences the connection stability between nodes in a mobile wireless network. Link instability has a significant impact on network connectivity and routing performance, which may result in a substantial effect on packet delivery ratio, network throughput, and increase end-to-end delay. Therefore, the basic principle of link stability prediction is to evaluate the link availability time image. We assume that network nodes follow the Random Waypoint mobility model [37] and the mobility speed is uniformly distributed between imagem/s. We define link available time as the time during which the link image is between a pair of wireless nodes from the time nodes come into one another’s communication range of transmission image RT, until the linkimage is lost due to node mobility. When image > RT, the time duration t reaches the maximum link duration.

To capture the random changes of the node movement image , which indicates the likelihood of the linkimage availability by the end of the image. It can be defined by the following expression [36,38]:

image (13)

λ−1 is the mean epoch of nodes; τ and ζ can be estimated by measurement.

Scalable opportunistic objective function

The concept of our proposed routing scheme is motivated by recent advances in networks science, namely, the small-world phenomenon, which supports the viability of our approach. Kleinberg [7] showed that in a large network, nodes are interconnected by a small number of hops (six degrees of separation) when they connect by a mixture of structured short-distance and random long-distance links.

In the same manner, in our routing scheme data packet moves toward its final destination in two different transmission methods; 1) by broadcasting the data packet locally within OD neighbor nodes to increase the probability of encountering a DE node without considering network scalability since it is local traffic and; 2) random long-range data packet transmission through DE links which move the packet closer to the final destination. Our mathematical investigation [2] proves that the proposed transmission scheme improves overall network scalability and reduces network performance degradation.

For the next-hop selection we proposed an objective function called SOOF for candidate selection. The proposed objective function captures DE link presence, node mobility, one hop throughput, and distance progress toward destination. The essential objective of SOOF is to enhance routing performance and increase network scalability by selecting the most stable candidates along the path. SOOF can be defined by the following expression (Table 3)

Parameter Acronym Value
Basic Bit Rate BBR 1 Mbps
Bit Rate BR 11 Mbps
PHY Header Size PHS 192 bits
MAC Header Size MHS 272 bits
Heads Transmission Time HTT PHS/BBR + MHS/BR
Acknowledge Transmission Time ACKT 112/BR + PHS/BBR
Short Interframe Space SIFST 10 s
Distributed Interframe Space DIFS 50 s

Table 3: IEEE 802.11 DSSS physical parameter set.

image (14)

image Is the velocity between the source node and the potential candidate nodes.

Candidate selection algorithm

The proposed opportunistic routing scheme relies on the SOOF metric, which runs hop-by-hop in a distributed pattern. The current packet custodian executes the candidate selection algorithm to select multiple local neighbors as potential for- warding candidates toward destination. The pseudo-code of the candidate selection is shown in Algorithm 1. The candidate selection can be performed as follows, assuming that node S wants to select its candidate set to reach the destination D. First, it creates an initial candidate set image which is determined based on the distance progress that local neighbors can achieve toward the final destination. A neighbor u of S is included in the initial candidate set image if the distance d (s, d ) > d (u, d ), then a subset of the initial candidate set is selected as the actual candidate. The best candidate among the nodes in the initial candidate set will be added to the actual candidate set, i.e. candidate image with max SOOF value. The sender S transfers the best candidate to the actual candidate set and removes it from the initial candidate set image The sender repeats the process to find the best candidates node in the initial set. The candidate selection algorithm stops for two reasons; 1) when there is no other suitable node in the initial set to be added to the actual candidate set and; 2) nodeS included the maximum number of candidates (ncand) into the actual candidate set.

Candidate coordination mechanism

Although all candidate nodes will receive a given packet at each hop, only one forwarding candidate carries out the forwarding process towards the destination. Researchers have proposed two classes of candidate coordination methods, namely Controlbased and Timer-based [32]. However, the proposed coordination mechanisms unsuitable for consideration in our routing scheme without customization, due to the variation in signal propagation between OD and DE. Signals in Omni-directional antenna propagate by broadcasting, and all neighbors within a forwarder’s transmission range will sense the transmitted signal, while the signal in DE uses unicast propagation, whereby neighbors cannot sense the forwarder transmitted signal. Therefore, OD candidates will not be aware of DE transmission, thanks to the long-range point- to-point transmission capability. Accordingly, we proposed a new coordination mechanism that meets the requirements of coordination transmission between OD and DE nodes. The proposed routing scheme includes two scenarios for candidate coordination:

Algorithm 1 Candidate Selection

image

2: N(S) = {i = neighbor(S) | dS,D < di,D}

3: for all i ∈ N(S) do . Creates the initial CS

4: if dS,D > di,D then

image

6: end if

7: end for

image

9: Calculate the transmission delay using formula (9);

10: Calculate the link duration using formula (13);

11: cand ← arg c∈ˆ CS,D i max SOOF (MLTS,i,<S,D CS )

12: temp ← maxmax SOOF (MLTS,i,<S,D CS )

13: if temp > c then

image

image

16: c ← temp

17: end if

18: end while

image

image

Coordination with DE node absence: A Timer-based coordination mechanism has been developed to provide a controlmessage- free between a forwarder and candidate set [32]. In this mechanism, coordination and data transmission are joined together to reduce network overhead and improve network scalability. To the candidate set that consists solely of OD nodes, we apply the timerbased coordination mechanism.

The forwarder node selects and ranks candidates based on the SOOF metric and includes the selected candidate address in the packet header. Based on the candidate’s relaying priorities, when a candidate receives a data packet, it waits a period of time image and forwards the packet based on the candidate’s order. Accordingly, the highest priority candidate forwards the received packet without waiting in the first time slot once it has received the packet correctly, while the remaining candidates listen to the channel before its transmission timer is expired to determine whether any of highest priority candidates have transmitted the packet or not (Figure 3). In this coordination scheme, the lower priority candidate can forward the packet only if the highest priority candidate has failed to relay the packet. This coordination methodology assumes that the candidates are within transmission range of one another; thus, when the highest priority candidate relays the packet the remaining candidate nodes simply discard it. We considered the timer-based coordination scheme since there is no need to inject any extra control packet into the network and minimize the initial delay that the highest priority candidate must allow to elapse before forwarding the packet, compared to the control-based coordination mechanism. The waiting timer here is an adjustable parameter, and it can be tuned depending on the network density and application characteristics.

Figure 3: Timer-based coordination.

Coordination with DE node presence: The communication process between DE nodes takes place in wireless point-topoint fashion; thus, OD neighbors will be unaware of any packet transmission that has been performed by DE candidates. Therefore, an extra Control Message Notification (CMN) is needed to notify OD candidates to discard the packet, without which the highest priority OD candidate will carry out the packet transmission process after waiting for x ( priority - 1)ms based on timer-based coordination.

Therefore, a coordination mechanism is required to inform OD candidates that the packet has just been sent out through the DE link and can be removed from storage. As mentioned, above, DE nodes are equipped with two kinds of antennas OD for short reliable communication and DE antenna for long-range communication. If a DE node present within a sender’s radio range, it will be the high priority candidate for relaying the sender packets, and the remaining OD candidates will be selected and assigned priorities depending on their SOOF values. We can avoid the need to transmit the extra control packet CMN by considering a wireless unicast transmission between the forwarder and DE candidate, in which the forwarder includes DE address only in the packet header. However, to minimize the relaying time and avoid the requirement for packet re-transmission if the DE candidate did not receive the packet or fail to relay it, the sender includes all candidates’ addresses in the packet header.

Implementation and Evaluation

Simulation setup

To evaluate the performance of the proposed routing scheme, we compared it with three other relevant routing protocols; DSDV, AODV, and GOR. We implement our routing scheme using ns-3 simulation. The mobile wireless network consists of 100 mobile OD nodes in a 2D environment, which is randomly distributed in a square with sides equal to 1000 m. Furthermore, the network includes extra 20% nodes uniformly distributed. The network nodes roam randomly according to the Random Waypoint (RWP) mobility model at a predefined speed, and no group mobility models are considered in this simulation. The OD nodes radio transmission range RT OD=100 m with a channel capacity of 2 Mbps, while the radio transmission range for DE nodes RT DE=5. RT OD,with a channel capacity of 10 Mbps [5].

In the simulation, the source node generates a constant bit rate (CBR) traffic, at a constant time interval with a packet payload size of 512 bps, it transmits packets for the simulation duration time of 100 seconds. We perform a set of 15 runs for each experiment to plot the average result. The remaining simulation parameters are listed in Table 4.

Parameter Acronym Value
Number of nodes NO 100
DE nodes ratio NE 20%
Simulation Area 1000 m × 1000 m
DE Transmission Range RT (DE) 100-500 m
OD Transmission Range RT (OD) 100 m
Maximum speed vmax 5-30 m/s
Packet size Sp 512B
Data rate DR 20 pps
Buffer size BS 0 packets

Table 4: Summary of our simulation parameters.

Evaluation metrics

We evaluate the performance of the proposed routing scheme by considering different metrics:

• Throughput: the rate of successfully delivered data packets per second over the communication channel from source to destination.

• Packet delivery ratio: measured as the ratio of packets successfully delivered to corresponding destination compared to the total number of data packets transmitted by the sender. This can be easily calculated by dividing the number of received data packets at the destination by the number of data packets that were transmitted by the sender.

• Routing protocol control message overhead: measured as the ratio of packets required to construct a path between two network pairs of nodes per successful data packet delivered at the destination.

Performance with varying nodes’ speed

The impact of nodes’ speed on network throughput is illustrated in Figure 4. Overall, the mobility of the nodes has a direct effect on the network throughput as a result of frequent link disconnection. AODV is associated with severe reduction in throughput as node mobility increases due to frequent loss of the path to the destination. GOR in the other hand, affected by assigning a candidate that is closer to the destination highest priority to relay the forwarder data packet since the higher Priority to relay the forwarder data packet since the higher distance progress node has low link delivery probability, and in most cases, it will not receive the transmitted packet correctly. By contrast, DSDV achieved better throughput than AODV and GOR, DSDV can converge faster the AODV due to the rapidly update breakage links along the path. However, the proposed routing scheme consistently performs better than DSDV, AODV, and GOR; this is due to its selection of the most stable links along the path to the destination. For example, the throughput in DSDV and AODV drops when the nodes’ mobility increases, while the proposed scheme exhibits stable throughput under high node mobility. Figure 5 illustrates the impact of the independent factor node mobility on the packet delivery ratio. We observe that the packet delivery ratio decreases drastically at higher node mobility in DSDV and AODV. This is a result of frequent link breakage, which requires the initiation of a route search to update the routing table. The time it takes to update the routing table increases the end-to-end packet delay and decreases the network throughput. Furthermore, by taking into consideration a real-time application in which the source node generates high constant bit rate traffic that increases the amount of packet injected into the network, the DSDV and AODV were unable to tolerate packets stream, and consequently the ratio of dropped packets is high due to high node mobility. By contrast, the proposed protocol is more resilient to frequent topology changes, thanks to the candidate selection mechanism which allows the construction of paths on the fly, which makes it independent of node mobility. Moreover, the presence of DE nodes creates shorter paths toward the destination, and that increases the probability of reaching the destination. In Figure 6, we report the control message overhead as a function of node mobility. DSDV and AODV exhibit increasing control message overhead as node mobility increases due to the increment of routing propagation update rates to meet the requirement of maintaining end-to-end accurate routes and stable links. As Figure 7 indicates, it is clear that a flat routing protocol such as DSDV and AODV are unscalable, and inappropriate for a dynamic network, which requires a rapid update. However, GOR and the proposed routing scheme exhibit better performance in terms of control message overhead than DSDV and AODV since the control message overhead is independent of nodes mobility and network topology change. In addition, the Hello packets are the only control message that network nodes exchange in our routing scheme.

Figure 4: Throughput versus varying nodes speed.

Figure 5: Packet delivery ratio versus varying nodes speed.

Figure 6: Overhead ratio versus varying nodes speed.

Figure 7: Throughput versus number of flows.

Performance with increasing the number of flows

The second experiment reports the impact of the increasing number of flows on the performance of the routing protocols. We observed that as the data flow increases, throughput and packet delivery ratio decrease drastically, and control massage overhead increases in DSDV and AODV. The rapid updating and exchange of the entire routing table with network nodes in DSDV significantly increases routing control message overhead, which in turn degrades the network performance, as Figure 8 illustrates. By contrast, AODV and GOR are more robust than DSDV in terms of routing protocol overhead. In AODV, the routing control message overhead was <15% that of DSDV, where the GOR shows constant level of control message overhead due to the routing control messages’ independence from user traffic and network topology change. On the other hand, packet delivery ratios in DSDV and GOR perform better than AODV. DSDV reacts relatively quickly to network topology changes and updates breakage links that may be affected. The better delivery ratio in DSDV comes at a higher delay cost than GOR (Figure 9). However, our proposed scheme outperforms all other routing protocols, by selecting the candidate with most stable link along the path that increases the packet delivery ratio and therefore maximizes network throughput. To further control the control message overhead and for the sake of network scalability, we consider the time-based coordination mechanism between candidate set nodes, where there is no need for an extra control message to relay the sender packet.

Figure 8: Overhead ratio versus number of flows.

Figure 9: Packet delivery ratio versus number of flows.

Performance with increasing the network size

The network throughput is the critical metric that illustrates network’s scalability. For a network to scale, its capacity should grow linearly with the number of nodes, and increased network size will not lead to performance degradation [2]. The main reason for the lack of scalability in routing protocols running on multihop wireless networks is that the packet has to travel long distances roughly n1/2 hops, causing the bandwidth resource consumption per packet to rise quickly as n increases. Figure 10 shows the throughput performance evaluation as a function of number of nodes. We vary the area in the simulation to keep node density consistent for all runs, as Table 5 indicates. We fix node mobility speed at 25 m/s and vary the number of nodes. When the network size is <100 nodes, all routing protocols cope with network topological changes and exhibit adequate performances. However, as the network size grows larger routing control messages drastically increase, which generates considerable overhead in DSDV and AODV. This is a consequence of the diminishing of the precomputed routes to the desired destinations due to the dynamic topology. Therefore, the throughput decreases linearly as the number of nodes increases. By contrast, the proposed routing scheme exhibits a constant level of throughput owing to the reduction in the distance that a transmitted packet must travel. Moreover, the basic design of our approach provides a relatively stable and scalable network infrastructure, upon which the opportunistic usage of DE links makes it possible to achieve capacity scaling by minimizing the long distance that a packet must travel by sending out the packet over DE links. This creates more shortcuts in the network to reach a corresponding destination, which prevents the bandwidth consumption from rising, and prevents the network from suffering performance degradation.

Figure 10: Throughput versus number of nodes.

Number of nodes Simulation area
25 500 × 500
50 700 ×700
100 1000 × 1000
225 1500 × 1500
324 1800 × 1800
400 2000 × 2000

Table 5: Node density (nodes versus area).

Conclusion and Future Work

In this paper, we have proposed a hybrid scalable opportunistic routing scheme for large-scale wireless networks. The proposed routing scheme novelties is presented with respect to both candidate selection algorithm, where a new metric called SOOF that captures DE links presence, one-hop throughput, node mobility, and expected distance progress to the destination, and the coordination mechanism, where two different coordination scheme were included, namely, time- based coordination schemes for OD candidate and control-based coordination for hybrid candidate DE/OD. The candidate selection algorithm intend to improve network connectivity and routing performance by leveraging the presence of DE links in the routing paths and their costs, which minimize the average distance that each data packet must travel previous delivering to the final destination. Awareness of the presence of DE links and leveraging DE links opportunistically are the crucial factors in providing a scalable large-scale network, with the absence of network topology information. We have compared the proposed routing schema with three other relevant routing protocols proposed in previous literature: DSDV, AODV, and GOR. Simulation results validated our analysis and demonstrated that the proposed routing scheme is able to scale and the increase of mobile nodes did not lead to network performance degradation. However, the relevant routing protocols performance failed to scale or cope whenever the network size increased, or network topology changed.

Acknowledgment

This work is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under contract/grant number W911NF-15-1-0393.

References

Track Your Manuscript

Recommended Conferences

Share This Page