In a multi-hop wireless network, connectivity is determined by the link that is established by the receiving signal strength computed by subtracting the path loss from the transmission power. Two path loss models are commonly used in research, namely two-ray ground and shadow fading, which determine the receiving signal strength and affect the link quality. Link quality is one of the key factors that affect network performance. In general, network performance improves with better link quality in a wireless network. In this study, we measure the network connectivity and performance in a shadow fading path loss model, and our observation shows that both are severely degraded in this path loss model. To improve network performance, we propose power control schemes utilizing link quality to identify the set of nodes required to adjust the transmission power in order to improve the network throughput in both homogeneous and heterogeneous multi-hop wireless networks. Numerical studies to evaluate the proposed schemes are presented and compared.
In a multi-hop wireless network, the nodes must cooperate to dynamically establish routes using wireless links and these routes must involve multiple hops with each node acting as a router. In many multi-hop wireless network scenarios, arbitrary node deployment or interference can change dynamically, resulting in topology changes. A multihop wireless network also inherits the traditional problems of wireless communications; this when combined with mobility and a lack of infrastructure makes the design and development of such a network challenging
. Connectivity is essential in any network for communication; it can be established if two nodes are within the communication range of each other in a wireless network. Unlike wired networks, links in wireless networks are unreliable because of the nature of their medium, air, which makes link quality susceptible to many factors such as noise, interference, and obstacles. Many researchers have studied the connectivity of multi-hop wireless networks in homogeneous conditions where nodes have identical properties and inhabit a uniform environment (e.g., identical transmission power, battery life, radio propagation ranges, and antennas). However, measurement studies
have shown that several of the assumptions in the homogeneous context are inaccurate. In particular, they have reported that real networks could have directional links. For example, if all the nodes have different transmission power, their transmission range differs and a directional link can be formed. Similarly, a directional link is formed by nodes having non-identical signal propagation due to differences in the local environment (e.g., trees and buildings). In
, we proposed methods to improve the connectivity of a multi-hop wireless network in a heterogeneous environment, with the focus on ensuring that the network was k-connected. In reality, the existence of a link between two nodes does not ensure that its quality is consistent in both directions and that the link quality is often asymmetric (e.g., different achievable bit rates in each direction). Note that a common approach to connection routing in a multi-hop wireless network is to base route selection on a link quality
metric. For example, the well-known link quality-based routing protocol, optimized link state routing protocol (OLSR) utilizes the expected transmission count metric (ETX)
A non-homogeneous wireless network environment makes the link quality unreliable, which results in connectivity change. We utilize the measured link quality and identify the corresponding connectivity change. Then, we identify nodes that need transmission power control to improve network performance (i.e., throughput). From the perspective of heterogeneity, we consider two factors, namely signal propagation and transmission power, to compare and evaluate network performance via a simulation study. Then, we propose cluster-based power control schemes that can improve network performance. OLSRETX has been widely used in many research studies. Gottron et al.
used OLSR-ETX for cluster-based architecture for a mobile peer-to-peer network. OLSR-ETX was also implemented in ultra-light intelligent flying robots in
. Its performance for different applications was studied in
. Several studies investigated the limitations of OLSR-ETX and proposed protocols or algorithms to overcome these shortcomings. Kulla et al.
proposed the BATMAN routing protocol for the synchronization problem. This protocol resolved the problem of topological message dissemination. Pinheiro et al.
modified ETX with queue availability by using fuzzy logic. In
, the ETX value was modified on the basis of MAC layer congestion sensing from the queue length to optimize the routing protocol at the network layer and enhance video streaming in an 802.11 wireless mesh network. Somasundaram et al.
tried to solve the problem of the set cover method in that it tends to select the unstable short-distance path rather than the more stable long-distance path to the destination where the distance is measured by the number of hops. They proposed the stable path topology control that uses ETX to solve this problem. However, the connectivity change based on the link quality measure has not been studied to the best of our knowledge. In this paper, we present the connectivity change based on the measured link quality and the corresponding performance degradation. Then, we propose transmission power control schemes to improve performance.
The rest of this paper is organized as follows: we define the network models in Section II and propose two clusterbased techniques to improve the network in Section III. Simulation results illustrating the effectiveness and tradeoffs of the resilience schemes are given in Section IV and discussed in Section V. Lastly, we present our conclusions in Section VI.
II. NETWORK CONNECTIVITY
Connectivity between a pair of nodes is established if they are within the communication range of the wireless multi-hop network. More specifically, the communication range is determined by the receiving signal strength, which can be computed using the transmission power and the path loss. The common propagation models are free space, tworay ground, and shadow fading. The free-space model is considered when the network environment is assumed to be an open space with no objects such as trees and buildings and no excessive noise. The two-ray ground model includes the signal reflected by the ground, but the environment is still assumed to be open without any object. In these models, the path loss gradually decreases with an increase in distance, which implies that connectivity is deterministic and is determined by the distance between the two nodes. If two nodes are within a certain range in which the receiving signal is still sufficiently good to receive data, they can communicate. Therefore, the packet loss in these propagation models occurs more likely not by the connectivity but by the traffic load. The heavy traffic load on the link may drop the packets due to the queue size. The shadow fading model is considered when the network environment includes any object that causes the random attenuation that affects the signal propagation, called shadow fading X, in the path loss model, as shown in Eq. (1).
) − 10log
denotes the transmitting power,
represents the receiving power at 1 m,
indicates the distance, and
denotes a random variable with a log-normal distribution whose probability density function is shown in Eq. (2).
denotes the mean received signal strength and
represents its standard deviation. Standard deviation
is the factor that determines the randomness of the shadow fading effect. Shadow fading heavily affects network connectivity. The connectivity of a wireless multi-hop network in a shadow fading environment is studied in
; this study has reported that connectivity is probabilistic and the probability of connectivity between two nodes dramatically decreases with an increase in distance. This connectivity behavior probabilistically produces the packet loss and affects the ETX value in OLSR. To illustrate the connectivity over the network, we randomly generate 40 of 50-node network topologies where the nodes are uniformly distributed over the area of 1,500×1,500 m
. The topologies are at least 1-connected in the unit disk graph (UDG) model with a transmission range of 250 m. The transmission power level of each node is set to 24.5 dBm. The receiving threshold is set to -64.4 dBm, which implies that the receiver receives the packet if the received signal strength at the receiver is greater than the threshold and this threshold falls in the transmission range of 250 m. We use an 802.11 wireless mesh network as the MAC layer protocol and OLSR as the routing protocol. Then, we compare the two-ray ground and shadow fading propagation models. For the connectivity comparison, we use the inverse of ETX values to determine the link connectivity depending on a pre-determined threshold value. The ETX value can be determined from the measured values of the forward and reverse links
, which can be computed by Eq. (3), where
denotes the forward delivery ratio and
represents the reverse delivery ratio.
We remove the poor links; therefore, the inverse of the ETX value is smaller than the threshold (i.e., 0.01, 0.03, and 0.05). Then, we examine the network connectivity for the 50-node network topologies in both propagation models. We observe that all network topologies are at least 1-connected in the two-ray ground propagation model, while none of them is 1-connected in the shadow fading propagation model.
We also compare the performance test of both propagation models via a simulation study using NS-2. We use the same network parameters and network topologies and randomly generate a constant bit rate (CBR) traffic of 1000 bytes every 0.25 seconds by using the user datagram protocol (UDP). The number of traffic connections is randomly selected on the basis of the mean number of connections (MC), which is the average ratio of the number of connections to the number of total possible connections (i.e.,
– 1)/2). Preference in the selection of the traffic is given to the pair of nodes that has a greater hop-count (i.e., longer path) in order to illustrate more effective performance evaluation. The starting time of the CBR traffic is randomly selected, and the throughputs are collected and measured after all the CBR traffic is established. Transmitting and receiving antenna gains (i.e.,
) are set to 1.0 and the frequency to 914 MHz. The heights of both the transmitting and the receiving antenna are set to 1.5 m. For the shadow fading model, we use a path loss exponent of
=2.7 and a deviation of
=4 dB. The throughput is computed by dividing the number of received packets by the given time (i.e., simulation time of 50 seconds). The average throughput results are compared in
with a 95% confidence interval at each MC (i.e., MC=0.1, 0.3, 0.5). The red line represents the average throughput of the network as obtained by the two-ray ground propagation model, and the blue line represents the results obtained by using the shadow fading propagation model. These results show that the network throughput drops significantly in the shadow fading propagation model. For example, the throughput drops from 304.73 to 35.337 packets/s at MC=0.1. Similar throughput drops are observed at MC=0.3 and 0.5. The difference in the throughput is 269.39 packets/s at MC=0.1, 313.14 packets/s at MC=0.3, and 312.16 packets/s at MC=0.5. The link quality changes in the shadow fading propagation model, which affects the network connectivity. Consequently, the network performance also degrades. Therefore, an improvement in network connectivity also improves the network performance.
Average throughput of two different propagation models for mean number of connection (MC)=0.1, 0.3, 0.5.
In this study, we mainly focus on the shadow fading propagation model in homogeneous and heterogeneous wireless networks in order to improve the network performance by adjusting the transmission power. In a homogeneous wireless network, all nodes have identical transmission power, whereas a heterogeneous wireless network has non-identical transmission power. Further, in this paper, we define two network models that ensure homogeneous transmission power and heterogeneous transmission power in the shadow fading propagation model, respectively.
III. TRANSMISSION POWER CONTROL SCHEME AND IMPLEMENTATION
Consider an arbitrary multi-hop wireless network of
), be the graph of the topology, where
denotes the set of nodes and
represents the set of links. The graph
can be represented by the
) at time
. Each element is the link connectivity between two nodes depending on the strength of the receiving signal that can be measured at the receiving node. The adjacency matrix
) can be determined from the link connectivity and the topology information periodically gathered by proactive or reactive routing protocols. Let
) denote the degree of node
. We define
as the diagonal matrix consisting of the degree of each node. The Laplacian matrix
) of a graph is defined in terms of the adjacency matrix
) and the nodal degree matrix
)). The eigenvalues
) form the Laplacian spectrum of the graph. The eigenvalues
and their associated eigenvectors
] can be computed from (L − λ
= 0 by using a number of wellknown efficient numerical methods. In algebraic graph theory
, zero is always an eigenvalue of
and the number of zero eigenvalues is equal to the number of connected components of the network
. Thus, the network is connected (i.e., at least 1-connectivity) if the Laplacian matrix of the topology has a single zero eigenvalue (i.e., if the second smallest eigenvalue is positive →
- A. Cluster-Based Transmission Power Control Scheme
We propose cluster-based transmission power control schemes to improve network performance. These schemes find low-quality links and identify the set of nodes to increase the transmission power. The cluster and its set of associating nodes can be determined by the eigenvalue and the eigenvector of the Laplacian matrix
. Once the sets of member nodes in each isolated cluster are identified, a cluster adjacency matrix,
, can be determined, which represents how the clusters are symmetrically or asymmetrically connected. The cluster adjacency matrix can be determined as follows:
denotes the set of nodes of each cluster
represents the network adjacency matrix. The proposed schemes use a cluster adjacent matrix to identify the set of nodes that require transmission power control. The first scheme is cluster merging with symmetric link quality(CMSLQ), which uses the inverse of the ETX value for link quality where the link quality matrix,
, is symmetric (i.e.,
). The other scheme is cluster merging with asymmetric link quality (CMALQ) that uses unidirectional link quality. Both schemes first identify the low-quality links and remove them to examine the network connectivity. If the network is not connected, it identifies the isolated clusters and the associated nodes in each cluster and finds the set of minimum-cost links between the isolated clusters. Then, it finds the minimum number of minimum-cost links to make the network at least 1-connected. Then, it identifies the set of nodes required to control the transmission power in order to improve the link quality. We consider the distance as the cost to find the minimum-cost link and the minimum-distance link can be selected where the node location can be obtained by using the global positioning system (GPS) or localization techniques
. The implemented CMSLQ algorithm is described in
Cluster merging with symmetric link quality
Cluster merging with symmetric link quality
CMALQ is similar but uses the forward and reverse delivery ratio instead of the inverse ETX. In general, these delivery ratios are not identical due to congestion, heterogeneity of node property, shadow fading effect, etc., which results in an asymmetric link quality matrix (i.e.,
). In the case of an asymmetric link, the connectivity test is not the same as that used in the case of a symmetric link. Therefore, we need another method to check for connectivity. We used the heterogeneous connectivity test described in
to check the network connectivity by validating the directional links; for any directional link, if two end nodes have a multi-hop path in the other direction, the link is validated and considered in the connectivity test. If the directed link is not validated, then it is removed in the connectivity test. Then, CMALQ is implemented to determine the minimum number of directed links that can connect isolated clusters.
IV. SIMULATION STUDY
In this section, we evaluate the improvement in network performance (i.e., throughput) brought about by the proposed cluster-based transmission power control schemes via a simulation study. We use an NS-2 simulator with at least 40 of the 1-connected 20-node network topologies where the nodes are uniformly distributed over an area of 680×680 m
. All other simulation parameters, such as the transmission and receiving power threshold, MAC and routing protocols, frequency, path loss exponent, deviation, and traffic load, are the same as those discussed in Section II. The transmission power at each node is randomly selected in the range of [23 dBm, 25 dBm] to produce the heterogeneity of the transmission power. Once the proposed schemes identify the nodes to improve the link quality, the transmission power at the selected node increases to 33 dBm.
- A. Performance Evaluation in the Case of Symmetric Links
In this section, we implement the proposed CMSLQ scheme to evaluate network performance. In each network topology, this scheme runs for a certain amount of time (i.e., 40 seconds) and the inverse values of the ETX values at each symmetric link are obtained. Then, the symmetric link quality matrix,
, is produced and CMSLQ processes it to identify the set of nodes required to increase the transmission power. In this comparison, we select two threshold values (i.e., 0 and 0.05). None of the links are removed when the threshold value is set to 0 and CMSLQ is applied. When the threshold value is set to 0.05 (i.e., the approximate expected transmission count in each direction is 4.5), any link that has an inverse of an ETX value of less than 0.05 is removed and CMSLQ is applied.
The average throughput results are compared in
illustrates the average throughput comparison under a homogeneous transmission power condition and shows that CMSLQ improves the throughput for both threshold values. The average throughput is approximately 55 packets/s when CMSLQ is applied. When CMSLQ is applied in the case of threshold value=0, the throughput improves by about 27% (i.e., 70 packets/s). The higher the threshold, the greater is the improvement in the throughput; e.g., CMSLQ with a threshold value of 0.05 shows 36% improvement (i.e., 75 packets/s). Under the heterogeneous network condition, the proposed scheme improves the throughput, but the improvement is not as good as that under the homogeneous network condition, as shown in
. CMSLQ with a threshold of 0 improves the throughput by about 23% (i.e., 68 packets/s), while CMSLQ with a threshold value of 0.05 does so by about 27% (i.e., 70 packets/s). We observe that in both cases, the throughput improves when CMSLQ is applied and an increase in the threshold value leads to greater performance improvement.
Average throughput comparison for the cases of no scheme and cluster merging with symmetric link quality (CMSLQ) with threshold of 0 and 0.05 in a homogeneous transmission power network environment.
Average throughput comparison for the cases of no scheme and cluster merging with symmetric link quality (CMSLQ) with threshold of 0 and 0.05 in a heterogeneous transmission power network environment.
- B. Performance Evaluation in the Case of Asymmetric Links
OLSR utilizes the link quality computed using Eq. (3), and the consequent represents the link quality with an absence of direction. In general, the link quality in one direction may not be the same as that in the other direction in a wireless network, particularly in a heterogeneous wireless network. Then, the link quality matrix,
, is not symmetrical anymore; it becomes asymmetrical. In this section, we discuss the application of the proposed schemes to a network with direct links by using an asymmetric link quality matrix measured at the MAC layer. We implement the HELLO packets in OLSR, which are sent periodically at each node. We count the number of received HELLO packets for a certain amount of time at each node in order to compute the link quality of the directed links. By using the obtained asymmetric link quality matrix (i.e.,
), CMALQ finds the set of nodes required to control the transmission power by identifying the set of directed links to be improved where the threshold is set to 0. The results are compared with the zero threshold of CMSLQ in
illustrates the average throughput in a homogeneous wireless network. Unlike CMSLQ, the average throughput improvement by CMALQ is not significant. The figure shows that the throughput improvement is about 7% (i.e., 59 packets/s) by CMALQ and 27% by CMSLQ. The results obtained when the heterogeneous transmission power is considered are shown in
. While the average throughput improvement by CMSLQ slightly changes in a different network environment, that by CMALQ remains almost the same. The results of CMALQ under both network conditions show the least significant throughput improvement. However, CMALQ selects fewer nodes for transmission power control than CMSLQ does.
Average throughput comparison in the cases of no scheme, cluster merging with symmetric link quality (CMSLQ) with zero threshold, and cluster merging with asymmetric link quality (CMALQ) in a homogeneous transmission power network environment.
Average throughput comparison in the cases of no scheme, cluster merging with symmetric link quality (CMSLQ) with zero threshold, and cluster merging with asymmetric link quality (CMALQ) in a heterogeneous transmission power network environment.
In this study, we evaluated the network performance in terms of throughput in the case of the shadow fading propagation model in two network environments by using a simulation study. The simulation results showed that the network performance degraded in the shadow fading propagation model. Both the proposed transmission power control schemes improved the network performance. CMSLQ improved the throughput significantly as the threshold value increased, but it might require higher computation time due to an increase in the number of isolated clusters.
CMALQ also improved the throughput but not as significantly as CMSLQ. However, relatively few nodes were used to increase the transmission power by CMALQ; therefore, it improved the throughput with minimal cost. In the case of CMALQ, the throughput might increase by the use of a relatively high threshold. CMSLQ was relatively easy to use with less computation time, while CMALQ required relatively large computation time.
Many 1-connected homogeneous wireless networks become disconnected probabilistically in the shadow fading propagation model; this degrades the network performance. In this paper, we proposed two transmission power control schemes to improve network connectivity in such a propagation model in the case of homogeneous and heterogeneous wireless networks. Our results revealed that both the proposed schemes improved the throughput; however, CMSLQ improved it more significantly than CMALQ. CMSLQ was also easier to implement with the drawback of a higher cost. Both schemes relieved the network degradation due to the shadow fading effect. However, CMALQ showed less improvement than CMSLQ. In the future, we intend to further investigate CMALQ by using a beam-forming or directional antenna for better linkquality improvement, which may, in turn, improve the network performance.
This work was funded in part by the US Army Research Office MURI grant W911NF-07-1-0318.
is an assistant professor at the School of Technology, Purdue University Calumet, IN, USA. He received his Ph.D. degree from School of Information Science, University of Pittsburgh, Pittsburgh, PA, USA, his M.S. in Telecommunications from University of Colorado, Bounder, CO, USA, and his B.S. in Mechanical Engineering from Oklahoma State University, Stillwater, OK, USA. His research interests are wireless sensor networks, survivable networks, and security. He is a member of IEEE.
is the Director of the Graduate Telecommunications and Networking Program and a faculty member at the University of Pittsburgh, Pittsburgh, PA, USA. He is a graduate of the University of Arizona, Tucson, AZ, USA (Ph.D.EE and M.S.SIE) and Virginia Tech, Blacksburg, USA (B.S.EE). His current research interests are survivable networks, performance analysis techniques, wireless/wired network design, and information assurance. Professor Tipper's research has been supported by grants from various government and corporate sources such as NSF, DARPA, NIST, IBM, ARO, and AT&T. His professional activities include serving as the General Chair of the 7th Design of Reliable Communication Networks Workshop (DRCN2009) and co-guest editor of a special issue of the journal Telecommunication Systems on Reliable Networks Design and Modeling, which was published in 2013. He is the coauthor of the textbook The Physical Layer of Communication Systems, published by Artech House in 2006. Further, he was the co-editor and a contributor to Information Assurance: Dependability and Security in Networked Systems, published by Morgan Kaufmann in 2008.
is an associate professor at the School of Information Science, University of Pittsburgh, Pittsburgh, PA, USA, where he regularly teaches courses on wireless networks and cryptography. From 2000 to 2005, he also served as the chair of the IEEE Communications Society Pittsburgh Chapter. His research interests include wireless network security, wireless data networks, position location in indoor wireless networks, and radio channel modeling for indoor wireless networks. He is a member of the IEEE.
Vehicular Networks, Techniques, Standards, and Applications.
Boca Raton, FL
Gray R. S.
“Experimental evaluation of wireless simulation assumptions,”
in Proceedings of the 7th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2004)
Kim T. H.
“Improving the connectivity of heterogeneous multi-hop wireless networks,”
in Proceedings of IEEE International Communications Conference(ICC)
“Performance comparison of FSR, LAR1 and LANMAR routing protocols in MANET’s,”
in Proceedings of the International Conference on Recent Trends in Business Administration and Information Processing (BAIP2010)
“Mobile ad hoc network routing protocols: a detailed performance examination of AODV, DSR and DSDV,”
International Journal of Computer Applications
DOI : 10.5120/7657-0761
“An efficient routing protocol for heterogeneous wireless ad hoc networks,”
in Proceedings of International Conference on Multimedia Technology (ICMT)
“Improving performance of a real ad-hoc network by tuning OLSR parameters,”
in Proceedings of the 10th IEEE Symposium on Computers and Communications (ISCC)
De Couto D. S.
“A highthroughput path metric for multi-hop wireless routing,”
DOI : 10.1007/s11276-005-1766-z
“A cluster-based localityaware mobile peer-to-peer architecture,”
in Proceedings of IEEE International Conference on Pervasive Computing and Communications Workshops
“Implementation of a wireless mesh network of ultra light MAVs with dynamic routing,”
in Proceedings of IEEE Globecom Workshop
“Comparison of two routing metrics in OLSR on a grid based mesh network,”
Ad Hoc Networks
DOI : 10.1016/j.adhoc.2008.04.006
“Performance evaluation of routing metrics for community wireless mesh networks,”
in Proceedings of 7th International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP)
van Stam G.
“Internet usage and performance analysis of a rural wireless network in Macha, Zambia,”
in Proceedings of the 4th ACM Workshop on Networked Systems for Developing Region (NSDR)
San Franciso, CA
“Performance comparison of OLSR and BATMAN routing protocols by a MANET testbed in stairs environment,”
Computers and Mathematics with Applications
DOI : 10.1016/j.camwa.2011.07.035
“A fuzzy queue-aware routing approach for wireless mesh networks,”
Multimedia Tools and Applications
DOI : 10.1007/s11042-011-0933-8
“Enhancing video streaming in 802.11 wireless mesh networks using two-layer mechanism solution,”
in Proceedings of AFRICON
“Distributed topology control for stable path routing in multi-hop wireless networks,”
in Proceedings of the 49th IEEE Conference on Decision and Control (CDC)
“Connectivity of wireless multihop networks in a shadow fading environment,”
DOI : 10.1007/s11276-005-3513-x
Algebraic Graph Theory.
New York, NY
“Ad-hoc networks beyond unit disk graphs,”
in Proceedings of the ACM Workshop on Foundations of Mobile Computing
San Diego, CA
Blum B. M.
Stankovic J. A.
“Range-free localization schemes for large scale sensor networks,”
in Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MOBICOM)
San Diego, CA