Journal of Machine to Machine Communications

Vol: 1    Issue: 3

Published In:   September 2014

On Applicability of the Assurance-Oriented Route-Split Routing Method for MANETs with Varying Node Density

Article No: 5    Page: 273-298    doi: https://doi.org/10.13052/jmmc2246-137X.135    

Read other article:
1 2 3 4 5

On Applicability of the Assurance-Oriented Route-Split Routing Method for MANETs with Varying Node Density

Received 21 October 2014; Accepted 6 June 2015; Publication 15 June 2015

Eitaro Kohno, Mario Takeuchi, Anri Kimura and Yoshiaki Kakuda

  • Graduate School of Information Sciences, Hiroshima City University, Hiroshima, Japan
  • E-mail: {kouno; kakuda}@hiroshima-cu.ac.jp;
    {mario; anri}@nsw.info.hiroshima-cu.ac.jp}


Abstract

Assurance network technologies are necessary to produce trustworthy terminals or infrastructure service applications for potentially large-scale networks such as in the Internet-of-Things. In large-scale network systems, not only the size of the network will become larger but also the density will vary in the network. Mobile ad hoc networks (MANETs) could be the future of networks. In the future, the size of networks will become larger. In real situations, nodes are not uniformly distributed in networks. The difference in node density will be greater in large-scale networks. When flooding is conducted in a dense area, network congestion occurs and nodes cannot communicate with each other.

As proposed in paper [1], Route-Split Routing (RSR) can communicate with a higher throughput than the Ad hoc On-demand Distance Vector (AODV) method in large MANETs. Along with the assurance network design principle, RSR splits its route by configuring Sub-route Management Nodes (SMNs) using a constant value called the SMN interval. In large MANETs, nodes are not distributed evenly. Thus, routing protocols for large MANETs must take into consideration that its route will pass through sparse areas and dense areas. In this paper, we propose a new routing method based on RSR for large MANETs with uneven node distribution by using the assurance network design principle. Our proposed method aims to avoid unnecessary rebroadcasts, contentions, and collisions caused by flooding in dense areas. To avoid the broadcast storm problem, we propose a new route repair method with RSR. Our proposed method can communicate with much higher throughput than RSR and AODV in a large MANET with non-uniform density. We have implemented our proposed method on a simulator and evaluated it through simulation experiments. We have observed that our proposed method is effective in large MANETs with uneven node distribution. The effectiveness of our proposed method varies with a configurable parameter called the SMN interval. Our proposed method with an SMN interval of 2 is the most effective among the tested SMN intervals 2, 5, and 8.



Keywords

  • Mobile ad hoc networks
  • Assurance networks
  • Opportunistic broadcast
  • Broadcast storm
  • Route-split routing

1 Introduction

Assurance networks and their design principle [24] are proposed to produce trustworthy terminals or infrastructure service applications for machine-to-machine communication such as in the Internet-of-Things. One of the issues when constructing assurance networks in MANETs is to provide timely services when the size of the networks changes. This will be referred to as the scalability issue. Mobile ad hoc networks (MANETs) [5, 6] are autonomous distributed networks. They consist of mobile terminals (hereinafter referred to as nodes) with routing functions. They can communicate with each other without fixed infrastructures such as base stations. MANETs can be used as an emergency network in a disaster area where the fixed infrastructures cannot be used. As proposed in paper [1], Route-Split Routing (RSR) [1] for large scale MANET has been extended to assurance networks [7, 8]. With RSR, nodes can communicate with a high throughput even when the number of hops between the source and the destination nodes is large. In real situations, nodes are not uniformly distributed in networks, and it is assumed that there are dense and sparse areas such as the inside and outside of buildings. When the distance between a pair of source and destination nodes is long, the route passes through some sparse areas and dense areas. However, flooding in dense areas can cause unnecessary rebroadcasts, contentions, and collisions if nodes share a common channel with carrier sense multiple accesses that do not have collision detection capabilities. The problems are defined as follows:

  • Unnecessary Rebroadcasts: when a node rebroadcasts a message to its neighbors, even though all its neighbors already have the message.
  • Contentions: when nodes receive rebroadcasted messages, these transmissions, which are all from nearby nodes, may contend with each other and reduce the transfer rate.
  • Collisions: when multiple data/control packets arrive at the same node and interfere with each other, causing data/control packet loss.

In flooding, data/control packet loss due to collisions is more likely to occur because flooding that is a chain reaction of broadcasts has no back-off mechanism, RTS/CTS dialogue, or collision detection mechanism.

In this paper, we propose an improved RSR for large MANETs with uneven density by alleviating the aforementioned problems in order to construct an assurance network [9].

2 Ordinary Routing and Assurance Routing for MANETs

To apply assurance-oriented design principle for Route-Split Routing method, we have to consider problems on large-scale MANETs. In Section 2.1, we address relationship routing methods that include Route-Split Routing method. In Section 2.2, we describe one of problems for large-scale MANETs, the “Broadcast storm” problem. Section 2.3 mentioned the concept of assurance networks and their design principles. Section 2.4 describes “assurance-oriented design for ad hoc networks” that is introduced in our proposed method.

2.1 Ad Hoc Networks and Route-Split Routing

Ad hoc networks [10, 11, 6] are autonomous distributed networks, which consist of wireless terminals or nodes. Ad hoc networks do not rely on a fixed or centralized communication infrastructure such as a base station or an access point. In ad hoc networks, nodes communicate directly with each other. When a node communicates with nodes beyond its radio communication range, intermediate nodes relay data/control packets. This relaying function is defined as multi-hop communication.

Ad hoc networks are categorized according to node attributes. They are (1) mobile ad hoc networks [10], (2) wireless sensor networks [1214] (3) wireless mesh networks [15], and (4) others [6].

Mobile ad hoc networks address the problem of node mobility. Node mobility can cause frequent breaks in the pre-established routes. To compensate for the route breaks, mobile ad hoc networks must enact route repair procedures. Currently, there are some standard protocols such as AODV [16, 17]. dynamic source routing (DSR) [18], destination-sequenced distance vector routing (DSDV) [19], optimized link state routing (OLSR) [20], and zone routing protocol (ZRP) [21]. These protocols are well designed to compensate for the drawbacks of mobile ad hoc networks. However, it has been noted that large-scale mobile ad hoc networks suffer from reduced effective bandwidth due to rebroadcasting. Those with greater than a few hundred nodes are especially affected by reduced effective bandwidth [22, 23]. To counter this, some methods have been proposed, such as clustering [24] and others [1, 25].

RSR [1] is an on-demand routing protocol based on AODV [16]. RSR splits its route by configuring Sub-route Management Nodes (SMNs) using a constant value called the SMN interval. The split routes between each pair of adjacent SMNs are maintained by the SMNs. Figure 1 shows an example of established routes with RSR. In Figure 1, nodes A and J are the source node and the destination node respectively. Nodes A, D, G, and J are SMNs, and they maintain the split routes between themselves and their neighboring SMNs. The SMN interval is set to three, which corresponds to the hop count between a pair of adjacent SMNs.

images

Figure 1 An example of established routes with RSR.

When a link is broken on a route, the RSR tries to repair the route locally by using a pair of adjacent SMNs. RSR can repair the route with fewer control packets than AODV because the local route between a pair of adjacent SMNs is shorter than the whole route. RSR can set a smaller value to the time to live (TTL) of the control packets that repair. In the case that the link between nodes E and F in Figure 1 is broken, the node which detects the break, node E, reports to its SMN, node D, using a route error message (RERR). When node D receives the RERR, it tries to repair the route between nodes D and G by flooding Repair Request (RepairREQ) packets. Then the TTL of RepairREQs is set using the SMN interval. RSR can locally repair the route and maintain its routes with fewer control packets than AODV because the SMNs have divided the route into shorter segments which have fewer nodes in need of repair. AODV would require all nodes to be repaired. If a local repair using RepairREQs fail a predetermined number of times, the SMN (node D) reports to the source node (node A) using RERR. Then node A reconstructs the route to the destination node (node J) using Route Request (RREQ) in a similar method to AODV.

2.2 Node Density and Broadcast Storm

In [26], Loong identified the relationship between connectivity and density. He evaluated AODV and DSR under a strenuous environment in which two dense clusters of source nodes must communicate despite being separated by a large sparsely populated area. According to [26], AODV and DSR can handle traffic by various applications but they are still far away from providing solutions for communication across networks with varying densities. Royer et al. tried to determine the optimum node density for delivering the maximum number of data packets in [27]. They concluded a global optimum density does not exist. However, according to Royer et al., the optimum number of average neighboring nodes was seven or eight for a stationary network, and the node density should increase as the mobility of the nodes increases.

The “broadcast storm” problem was identified in [28]. Broadcast storms include serious redundancy, contention, and collision problems which are caused by straightforward broadcasting. In broadcast storms, radio signals overlap with others in a geographical area. A comprehensive comparative analysis has been done in [29]. Broadcast techniques are categorized into four types: simple flooding, probability-based methods, area-based methods, and neighbor-knowledge methods. On probability-based methods, nodes retransmit based on random number generation. Area-based methods transmit over the geographical coverage area regardless of the presence of nodes within that area. In neighbor-knowledge methods, each node has knowledge of its 1-hop neighbors, which is obtained via periodic “Hello” packets. Each broadcast packet has a list of known neighbors of the broadcasting node. When a node receives a broadcast packet, it compares its own neighbor list to that of the sender. If the node cannot deliver to any additional nodes, it refrains from rebroadcasting. Otherwise, the node rebroadcasts the packet. Tseng et al. proposed several methods which are categorized into probability-based methods or area-based methods and evaluated them by simulation in [30]. In [31, 32], a dynamic probabilistic routing algorithm which is based on AODV is proposed. Using the algorithm, nodes retransmit with dynamically changing probability. The probability is determined using the number of neighbor nodes which is acquired by the exchange of “Hello” packets. Therefore dense areas will have nodes that are less likely to rebroadcast, and sparse areas will have nodes that are more likely to rebroadcast. In [33], Cartigny et al. proposed a combination of a probabilistic and a neighbor-knowledge scheme. When nodes receive a broadcast packet, they determine whether or not to retransmit it. In this scheme, nodes exchange the neighbor node list, and nodes which are close to the border of the radio area retransmit. Zhang proposed a combination of probabilistic and neighbor-knowledge methods in [12]. This method does not need a periodic exchange of “Hello” packets to acquire neighbor knowledge. It uses a packet counter to estimate its neighbor density.

2.3 Assurance Networks and their Design Principles

As we mentioned in Section 1, assurance networks [2, 3] are designed to produce trustworthy terminals or infrastructure service applications for the Internet-of-Things. Kakuda et al. describe assurance networks in [2, 3] as follows: assurance in distributed systems and networks is defined as the capability of guaranteeing functional and non-functional system properties such as dependability, security, timeliness and adaptability to heterogeneous and changing requirements. Assurance networks are also defined as those that provide timely services even with the following issues; (1) the size of the networks changes (scalability issues), (2) the requirements and environments of the networks dynamically change (dynamicity issues), (3) cyber-attacks occur (security issues) and (4) there are faults that may cause failures (fault-tolerance issues). Since assurance networks are very effective in coping with the four aforementioned issues, they will be vital to future networks such as in machine-to-machine communication systems.

Assurance network design principles are proposed by Kakuda et al. [4]. According to [4], the assurance network design principles consist of the autonomous network partition and integration method, as well as the self-organized real-time control method for changing environments.

In [4], Kakuda et al. describe assurance networks and show an example of assurance-oriented cluster-based power control method for MANETs. This is an example of an assurance-oriented design that deals with the scalability issue.

2.4 Assurance-Oriented Design for Ad Hoc Networks

Along with assurance networks, ad hoc networks show promise for their prospective users in future networks such as in machine-to-machine communication systems. Research has shown ad hoc networks work well in limited areas such as networks with less than a few hundred nodes. In future machine-to-machine communication networks such as in the Internet-of-Things, networks will have to handle more than a few hundred nodes. In addition, machine-to-machine communication systems have to show resilience against environmental changes. To meet these requirements, ad hoc networks should enact sound methodologies against security threats, fault-tolerance/dependability issues, and scalability problems. In paper [7], Takeuchi et al. propose assurance-oriented route-split routing against node faults to alleviate battery exhaustion. In this method, every node constantly monitors its own battery state and role. When a node is an SMN and its battery charge is low, the node attempts to reassign SMN status to an adjacent normal node.

In this paper, we propose a new assurance-oriented design for large-scale ad hoc networks using concrete examples. Our proposal provides solutions to the problems caused by dense and sparse areas in large networks.

3 Proposed Method

In this paper, along with assurance networks and their design principles, we proposed an assurance enhanced RSR for large MANETs where nodes are distributed unevenly. In our proposed method, we assess average throughput and varying node density as measurements of performance metrics and environmental change, respectively. Our proposed method aims to avoid unnecessary rebroadcasts, contentions, and collisions caused by flooding in dense areas.

To avoid the broadcast storm problem, we propose a new route repair method with RSR. In the preliminary experiment, we observed a broadcast storm caused by RepairREQs in RSR. Our proposed method prevents nodes from unnecessarily forwarding RepairREQs in dense areas. Our proposed method has the following two parts:

  • Estimation of surrounding node density
  • Broadcast storm avoidance

3.1 Estimation of Surrounding Node Density

RSR has two types of broadcast control packets, one is RREQ and the other is RepairREQ. RREQs are used for initial route construction and route re-construction after local repair failure. RepairREQs are used for local repair between adjacent SMNs. Surrounding node density is represented as the number of neighboring nodes. Nodes estimate the number of neighboring nodes from the number of received RREQs. This estimate tends to be proportional to the actual number. The estimated number of neighboring nodes is denoted as the numOfNeighbors and is calculated as follows:

Initialization:

Our proposed method employs a value denoted as the tentativeNumOfNeighbors to estimate the number of neighboring nodes. The initial value is 0.

Handling received RREQs:

When nodes receive a RREQ, they calculate the tentativeNumOfNeighbors. To avoid redundantly counting nodes, there is a built-in checklist that prevents counting neighboring nodes twice.

Estimation of the surrounding node density:

The estimation of the numOfNeighbors is calculated by a node which sets the TentativeNumberOfNeighbors. The tentativeNumOfNeighbors then updates the numOfNeighbors and resets to 0.

3.2 Broadcast Storm Avoidance

RSR causes broadcast storms by RepairREQ flooding. When nodes receive RepairREQs, they decide whether or not to forward them based on the estimated surrounding node density calculated by the method described in Section 3.1. This method avoids the RepairREQ flooding problem. Nodes in sparse areas always forward RepairREQs. In dense areas, our proposed broadcast storm avoidance mechanisms are enabled. Some nodes forward RepairREQs and the others do not. The algorithm to decide whether or not to forward the RepairREQs is shown in Figure 2. The algorithm has four input values. Two of them, the threshold and the idealNumOfForwardNodes, are configurable values. The numOfNeighbors is the estimated number of neighboring nodes calculated by the method described in Section 3.1. SMNs resend RepairREQ when they fail to repair their routes. The numOfRetriesLocalRepair is the number of resends of the received RepairREQ. Nodes can calculate the numOfRetriesLocalRepair by comparing the number of RepairREQs they have received to the previous value of numOfRetriesLocalRepair. This is used to increase the number of forwarding nodes in order to raise the probability of local repair success.

images

Figure 2 Pseudo code of algorithm for decision to forward RepairREQ based on node density.

4 Simulation Experiments

4.1 Simulation Environment

To evaluate our proposed method in networks which have nodes distributed unevenly, we conducted simulation experiments and compared the results of AODV, RSR, and our proposed method. The SMN interval is set to 2, 5, and 8. Both threshold and idealNumOfForwardNodes are set to 8 in our proposed method.

We made a network field with dense and sparse areas as shown in Figure 3. The network field is based on a scenario where a lot of people are crowded in dense areas such as buildings and try to establish communication with those in other buildings across a large sparse distance. The four small dense areas have 200 nodes each for a total of 800 nodes. The larger sparse area has 1700 nodes with the average of nodes within radio range. We put three source and destination nodes into each dense area. Each pair of source and destination nodes communicates over the sparse area as illustrated by the arrows in Figure 3. Table 1 shows the parameters for the simulation experiments. In the experiments, the number of the source and destination nodes does not change. We set the maximum node speed to 0 or 1 [m/s] to confirm the basic performance of our proposed method in both a static environment and a dynamic environment. In the dynamic environment, the nodes in a dense area move only in the dense area, and the nodes in the sparse area move all over the network field. The pause time of a node in the random waypoint model is 0. For the MAC layer protocol, we employed IEEE802.11b without RTS/CTS. The number of nodes and the field size are fixed.

images

Figure 3 Network field.

Table 1 Parameters for the simulations

Simulator QualNet ver.5.02 [34]
Field size [m x m] 6500 × 6500
Total number of nodes 2500
Number of nodes in sparse area 1700
Number of nodes in each dense area 200
Number of source and destination pairs 12
Mobility model Random Waypoint Model [30, 35].
Pause time [s] 0
Max. node speed [m/s] 0, 1
Application CBR
Data packet size [Byte] 512
Number of packet sends 1000
Interval time for packets [s] 0.10
Transmission range [m] 250
Bandwidth [Mbps] 11

4.2 Results

Figure 4 shows the average throughput and Figure 5 shows the total amount of control packets. The vertical axes are throughput and the amount of control packets, respectively, and the horizontal axes are the maximum node speed. The error bars show the ranges of error at 95 percent confidence intervals.

images

Figure 4 Average throughput.

images

Figure 5 Total amount of control packets.

In Figure 4, the static environment was a maximum node speed of 0 [m/s]. Our proposed method gets much higher throughput than RSR and AODV. The throughput increases by 117, 418, and 628 [%] over RSR when the SMN interval is 2, 5, and 8 respectively. RSR and our proposed method have a tendency to get a higher throughput when the SMN interval is smaller. Nodes barely communicate with AODV because the number of hops between the source and the destination nodes is 28 on average. This is too many hops for AODV. In Figure 5, the total amount of control packets in our proposed method decreases to 71.5, 68.6, and 52.6 [%] below RSR when the SMN interval is 2, 5, and 8 respectively. This shows that our proposed method alleviates broadcast storms. That said, the degree of alleviation is less when the SMN interval is large. Consequently, our proposed method and RSR use more control packets, the reason been that the SMN interval is used for setting the TTL of the RepairREQ.

In the case of a dynamic environment where the maximum node speed is 1 [m/s], nodes barely communicate with RSR. This is because control packet congestion causes broadcast storms. In the simulation environment the bandwidth is 11 [Mbps], and the amount of control packets indicates it is sent at about 9.68 to 9.87 [Mbps] on average. Hence, nodes hardly communicate with other nodes using RSR in all of the three SMN intervals. Nodes with AODV also hardly communicate because of congestion: the same as in the static environment. The throughput of our proposed method increases to 1068, 530, and 119 [%] over RSR, and the total amount of control packets also decreases to 78.3, 21.5, and 2.16 [%] below RSR when the SMN interval is 2, 5, and 8 respectively. Our proposed method uses fewer control packets and gets higher throughput when the SMN interval is smaller. However, when the SMN interval is 8, our proposed method is affected by the same broadcast storm problems as RSR. In addition, the amount of control packets exchanged is about the same as with RSR. Thus, our proposed method does not work effectively when the SMN interval is 8 in a dynamic environment.

In this network environment, where the SMN interval is 2, our proposed method decreases broadcast storms, reduces control packets dramatically, and gets the highest throughput.

5 Discussion

By reducing unnecessary packet forwarding, our proposed method aims to avoid broadcast storms caused by flooding in a dense area. To discuss the effect of control packet reduction in our proposed method, we observed the amount of RepairREQs in the dense areas and the sparse area. Figure 6 and Figure 7 show the amount of RepairREQ forwarded in the dense and sparse areas respectively. The vertical axes are the amount of RepairREQ forwarded, and the horizontal axes are the maximum node speed. The error bars show the ranges of error at 95 percent confidence intervals.

images

Figure 6 Amount of forwarded RepairREQ in the dense area.

images

Figure 7 Amount of forwarded RepairREQ in the sparse area.

Figure 6 shows the amount of forwarded RepairREQs in the dense areas is reduced with our proposed method. The amount of forwarded RepairREQs is between 81.3 to 88.8 [%] less than RSR in the static environment. In the simulation environment, our proposed method can reduce the amount of forwarded RepairREQs in dense areas up to about 96 [%] when idealNumOfForwardNodes is set to 8 and each node in the dense areas has around 200 neighboring nodes. Our proposed method produced fewer control packets than RSR and AODV in the simulation experiment. Our proposed method behaves about the same as RSR in the sparse area because we set the threshold to 8 and the average number of neighboring nodes in the sparse area to 7. However, Figure 7 shows the amount of forwarded RepairREQs with our proposed method also decreased in such a sparse area. This is caused by the reduction of the number of initiated RepairREQs. RSR caused broadcast storms, and frequently re-initiated RepairREQs after route repair failures. On the other hand, our proposed method avoids broadcast storms and repairs route breaks more easily. As a result, our proposed method also reduced the amount of RepairREQs leaked into the sparse area.

Figure 6 shows the amount of forwarded RepairREQs in a sparse dynamic environment with our proposed method. The amount of forwarded RepairREQs decreased to between 59.0 to 71.5 [%] less than RSR when the SMN interval was 5 and 8. When the SMN interval was 2, the forwarded RepairREQs were 92.4 [%] fewer. Figure 7 indicates that in a dynamic environment where the SMN interval is 2, our proposed method reduces forwarded RepairREQs by 89.9 [%] compared with RSR. As we described in Section 4, our proposed method with an SMN interval of 8 causes congestion. Similarly, with an SMN interval of 5, our proposed method nearly causes congestion. In the dynamic environment, our proposed method is effective only when the SMN interval is 2. However, where the SMN interval is 2, our proposed method reduced the number of control packets and achieved a much higher throughput than both RSR and AODV.

6 Effect of Proposed Method under Varying Densities

As we mentioned in Section 1, papers [2, 3] explained that maintaining performance under varying environmental changes is one of the important elements of assurance networks. We also conducted simulation experiments under varying network densities. In these experiments, we assume that these networks exist in an environment with varying densities. We prepared two network configurations: one with high density areas of 100 nodes, and the other with high density areas of 300 nodes in Section 6. We measured the amount of control packets, the data delivery ratio, and the average throughput of the original RSR and our proposed method.

Figure 8 to Figure 11 show the results of the following configurations: the node count in each dense area is 100 nodes with RSR; the node count in each dense area is 300 nodes with RSR; the node count in each dense area is 100 nodes with our proposed method; the node count in each dense area is 300 nodes with our proposed method.

images

Figure 8 Node count in each dense area is 100 nodes with RSR.

images

Figure 9 Node count in each dense area is 300 nodes with RSR.

images

Figure 10 Node count in each dense area is 100 nodes with our proposed method.

images

Figure 11 Node count in each dense area is 300 nodes with our proposed method.

Figure 8 to Figure 11 compare the average throughputs. Unlike RSR, the average throughput can be maintained in our proposed method. In dense areas with 300 nodes, the average throughput became unstable or was significantly reduced. According to the results of both the total amount of control packets and the data delivery ratio, RSR consumed more bandwidth. However, our proposed method did not consume as much bandwidth as RSR. Our proposed method was designed to reduce the likelihood of broadcast storms. According to our results, our proposed method met this criteria.

7 Conclusion

In this paper, along with assurance networks and their design principles, we proposed an assurance enhanced RSR for large MANETs where nodes are distributed unevenly. In our proposed method, we assess average throughput and varying node density as measurements of performance metrics and environmental change, respectively. Our proposed method aims to avoid unnecessary rebroadcasts, contentions, and collisions caused by flooding in dense areas. To achieve this aim, nodes in our proposed method estimate their surrounding node density without any additional control packets and determine whether or not to forward broadcast packets with our proposed method. We conducted simulation experiments and observed the effectiveness of our proposed method. Our proposed method can communicate with much higher throughput than RSR and AODV in a large MANET with non-uniform density. The effectiveness of our proposed method varies with a configurable parameter called the SMN interval. Our proposed method with an SMN interval of 2 is the most effective among the tested SMN intervals 2, 5, and 8.

Acknowledgements

This research is supported by JSPS KAKENHI Grant Number (B) (No.24300028), and (C) (No.25330109). This research is also supported by the Ministry of Internal Affairs and Communications under SCOPE Grant (Research & Development for Creation of ICT Innovation) No.131408006; by The Telecommunications Advancement Foundation (TAF), Japan.

References

[1] T. Mizumoto, T. Ohta, and Y. Kakuda, “Route-split routing resilient to simultaneous failure for mobile ad hoc networks,” IEICE Transactions on Fundamentals, vol. E91-A, no. 7, pp. 1625–1633, Jul. 2008.

[2] Y. Kakuda and M. Malek, “A united design model for assurance networks and its application to mobile ad hoc networks,” in Proceedings of the 10th IEEE international symposium on Autonomous Decentralized Systems (ISADS 2011) at the 10th international workshop on Assurance in Distributed Systems and Networks (ADSN2011), pp. 637–644, Apr. 2011.

[3] Y. Kakuda, “Assurance networks: concepts, technologies, and case studies,” in Proceedings of the second international symposium on Multidisciplinary Emerging Networks and Systems (MENS2010), pp. 311–315, Oct. 2010.

[4] Y. Kakuda, T. Ohta and R. Oda, “A methodology for real-time self-organized autonomous clustering in mobile ad hoc networks,” Concurrency and Computation: Practice and Experience, John Wiley & Sons, Ltd., vol.24, no.16, pp.1840–1859, Aug. 2012.

[5] C.-K. Toh, Ad Hoc Mobile Wireless Networks: Protocols and Systems. Prentice Hall, Dec. 2001.

[6] C.R. Murthy and B. Manoj, Ad hoc wireless networks: architectures and protocols, Prentice Hall, 2004.

[7] M. Takeuchi, E. Kohno, T. Ohta, and Y. Kakuda, “Improving assurance of a sustainable route-split MANET routing by adapting node battery exhaustion,” Telecommunication Systems (Special issue on multi-disciplinarily inspired networks and systems), vol.54, no.1, pp.35–45, Sept. 2013. [Online]. Available: http://link.springer.com/ article/10.1007/s11235-013-9714-1

[8] M. Takeuchi, E. Kohno, T. Ohta, and Y. Kakuda, “An extended micro loop routing for adapting to energy consumption,” in Proceedings of the second international symposium on Multidisciplinary Emerging Networks and Systems (MENS2010), pp. 334–339, Oct. 2010.

[9] E. Kohno, M. Takeuchi, A. Kimura and Y. Kakuda, “An assurance oriented route-split routing for MANET with non-uniform node density,” Proc. 8th International Conference on Broadband Communications and Biomedical Applications (IB2COM2013), pp.66–71, Dec. 2013.

[10] J. Wu and I. Stojmenovic, “Guest editors’ introduction: Ad hoc networks,” IEEE Computer, vol.37, no.2, pp.29–31, 2004.

[11] C.E. Perkins, Ad Hoc Networking, Addison-Wesley, 2001.

[12] I. Stojmenovi’c, ed., Handbook of Sensor Networks: Algorithms and Architectures, John Wiley & Sons, 2005.

[13] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, vol.38, no.4, pp.393–422, March 2002.

[14] R. Verdone, D. Dardari, G. Mazzini, and A. Conti, Wireless Sensor and Actuator Networks: Technologies, Analysis and Design, first ed., Academic Press, 2007.

[15] I.F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: a survey,” Computer Networks, vol.47, no.4, pp.445–487, 2005.

[16] C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (AODV) routing,” RFC 3561 (Experimental), Internet Engineering Task Force, Jul. 2003.

[17] C.E. Perkins and E.M. Royer, “Ad-hoc on-demand distance vector routing,” Proceedings of the Second IEEE Workshop on Mobile Computing Systems and Applications, pp.90–100, Feb. 1999.

[18] D.B. Johnson and D.A. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Mobile Computing, pp.153–181, Kluwer Academic Publishers, 1996.

[19] C.E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” ACM SIGCOMM Computer and Communication Review, vol.24, no.4, pp.234–244, Oct. 1994.

[20] T. Clausen, C. Dearlove, P. Jacquet, and U. Herberg, “The optimized link state routing protocol version 2,” RFC7181, Apr. 2014.

[21] Z.J. Haas, M.R. Pearlman, and P. Samar, “The zone routing protocol (ZRP) for ad hoc networks.” draft-ietf-manet-zone-zrp-04.txt, July 2002.

[22] J. Eriksson, M. Faloutsos, and S.V. Krishnamurthy, “DART: Dynamic address routing for scalable ad hoc and mesh networks,” IEEE/ACM Transactions on Networking, vol.15, no.1, pp.119–132, Apr. 2007.

[23] M. Caleffi, G. Ferraiuolo, and L. Paura, “Augmented tree-based routing protocol for scalable ad hoc networks,” Proceedings of the Third IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS’07), pp.1–6, Oct. 2007.

[24] J.Y. Yu and P.H.J. Chong, “A survey of clustering schemes for mobile ad hoc networks,” IEEE Communications Surveys & Tutorials, vol.7, no.1, pp.32–48, 2005.

[25] T. Ohta, T. Mizumoto, and Y. Kakuda, “Enhanced route-split routing tolerant to multiple concurrent link failure for mobile ad hoc networks,” Ad Hoc Networks, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 2010, vol.28, pp.284–299, Springer, Sept. 2009.

[26] O. H. Loong, “Evaluation of reactive mobile ad hoc wireless networks over different topological network node densities,” in Proceedings of the 2006 International Conference on Computing Informatics (ICOCI ’06), pp. 1–6, Jun. 2006.

[27] E. Royer, P. Melliar-Smith, and L. Moser, “An analysis of the optimum node density for ad hoc mobile networks,” in Communications, 2001. ICC 2001. IEEE International Conference on, vol. 3, pp. 857–861, 2001.

[28] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” Wireless Networks, vol. 8, no.2/3, pp. 153–167, 2002.

[29] B. Williams and T. Camp, “Comparison of broadcasting techniques for mobile ad hoc networks,” in Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing (MobiHoc ’02), pp. 194–205, 2002,

[30] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, “A performance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceedings of the fourth annual ACM/IEEE international conference on Mobile Computing and Networking, pp. 85–97, Oct. 1998.

[31] E. Natsheh and K. Buragga, “Density based routing algorithm for sparse/dense topologies in wireless mobile ad-hoc networks,” American Journal of Engineering and Applied Sciences, vol. 3, no. 2, pp. 312–319, 2010.

[32] E. Natsheh and K. Buragga, “Nodes density and broadcast management in heterogeneous environments of mobile ad-hoc networks,” Journal of Computer Science, vol. 6, no. 3, pp. 312–319, 2010.

[33] J. Cartigny and D. Simplot, “Border node retransmission based probabilistic broadcast protocols in ad-hoc networks,” in Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS’03), vol. 9, 10 pages, 2003.

[34] Scalable Network Technologies Inc., “Qualnet network simulator by scalable network technologies,” 2013. [Online]. Available: http://www.scalable-networks.com/

[35] J. Yoon, M. Liu, and B. Noble, “Random waypoint considered harmful,” in Proceedings of the 22nd annual joint conference of the IEEE Computer and Communications (INFOCOM 2003), vol. 2, pp. 1312–1321, Apr. 2003.

Biographies

Image

E. Kohno received his B.E. degree from Hiroshima Institute of Technology, Japan in 1990. He received his M.Sc. degree from Tokyo Institute of Technology, Japan in 1992, and belonged to their Doctoral course from 1992 to 1996. He received his Ph.D. degree from Tokyo Metropolitan University, Japan in 2012. He is currently a Lecturer in the Graduate School of Information Sciences, Hiroshima City University, Japan. His current research interests include network software. He is a member of IEEE (USA), the Institute of Electronics, Information and Communication Engineering (EIC, Japan), and the Information Processing Society of Japan (IPSJ, Japan).

Image

M. Takeuchi received his B.E., M.Sc. and Ph.D. degrees from Hiroshima City University, Japan, in 2009, 2011 and 2013, respectively. His current research interests include ad hoc networks. He is a member of the Institute of Electronics, Information and Communication Engineering (EIC, Japan).

Image

A. Kimura received her B.E. and M.Sc. degrees from Hiroshima City University, Japan, in 2011 and 2013, respectively. Her current research interests include ad hoc networks.

Image

Y. Kakuda received his B.E., M.Sc. and Ph.D. degrees from Hiroshima University, Japan in 1978, 1980 and 1983, respectively. From 1983 to 1991, he was with the Research and Development Laboratories, Kokusai Denshin Denwa Co., Ltd. (KDD). He joined Osaka University from 1991 to 1998 as an Associate Professor. He is currently a Professor in the Graduate School of Information Sciences, Hiroshima City University. His current research interests include network software engineering, assurance networks and mobile ad hoc networks. He is a member of IEEE (USA), the Institute of Electronics, Information and Communication Engineering (EIC, Japan), and the Information Processing Society of Japan (IPSJ, Japan). He received the Telecom System Technology Award from Telecommunications Advanced Foundation in 1992.

Abstract

Keywords

1 Introduction

2 Ordinary Routing and Assurance Routing for MANETs

2.1 Ad Hoc Networks and Route-Split Routing

images

2.2 Node Density and Broadcast Storm

2.3 Assurance Networks and their Design Principles

2.4 Assurance-Oriented Design for Ad Hoc Networks

3 Proposed Method

3.1 Estimation of Surrounding Node Density

3.2 Broadcast Storm Avoidance

images

4 Simulation Experiments

4.1 Simulation Environment

images

4.2 Results

images

images

5 Discussion

images

images

6 Effect of Proposed Method under Varying Densities

images

images

images

images

7 Conclusion

Acknowledgements

References

Biographies