![](/images/graphics-bg.png)
More Benefits of Adding Sparse Random Links to Wireless Networks : Yet Another Case for Hybrid Networks
Author
Source
International Journal of Distributed Sensor Networks
Issue
Vol. 2012, Issue 2012 (31 Dec. 2012), pp.1-12, 12 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2012-06-21
Country of Publication
Egypt
No. of Pages
12
Main Subjects
Telecommunications Engineering
Information Technology and Computer Science
Abstract EN
We theoretically and experimentally analyze the process of adding sparse random links to random wireless networks modeled as a random geometric graph.
While this process has been previously proposed, we are the first to prove theoretical bounds on the improvement to the graph diameter and random walk properties of the resulting graph as a function of the frequency of wires used, where this frequency is diminishingly small.
In particular, given a parameter k controlling sparsity, any node has a probability of 1/k2nr2 for being a wired link station.
Amongst the wired link stations, we consider creating a random 3-regular graph superimposed upon the random wireless network to create model G1, and alternatively we consider a sparser model G2 as well, which is a random 1-out graph of the wired links superimposed upon the random wireless network.
We prove that the diameter for G1 is O(k+log(n)) with high probability and the diameter for G2 is O(klog(n)) with high probability, both of which exponentially improve the Θ(n/log n) diameter of the random geometric graph around the connectivity threshold, thus also inducing small-world characteristics as the high clustering remains unchanged.
Further, we theoretically demonstrate that as long as k is polylogarithmic in the network size, G1 has rapidly mixing random walks with high probability, which also exponentially improves upon the mixing time of the purely wireless random geometric graph, which yields direct improvement to the performance of distributed gossip algorithms as well as normalized edge connectivity.
Finally, we experimentally confirm that the algebraic connectivities of both G1 and G2 exhibit significant asymptotic improvement over that of the underlying random geometric graph.
These results further motivate future hybrid networks and advances in the use of directional antennas.Erratum to “More Benefits of Adding Sparse Random Links to Wireless Networks: Yet Another Case for Hybrid Networks”dx.doi.org/10.1155/2012/730597
American Psychological Association (APA)
Ercal, Gunes. 2012. More Benefits of Adding Sparse Random Links to Wireless Networks : Yet Another Case for Hybrid Networks. International Journal of Distributed Sensor Networks،Vol. 2012, no. 2012, pp.1-12.
https://search.emarefa.net/detail/BIM-465914
Modern Language Association (MLA)
Ercal, Gunes. More Benefits of Adding Sparse Random Links to Wireless Networks : Yet Another Case for Hybrid Networks. International Journal of Distributed Sensor Networks No. 2012 (2012), pp.1-12.
https://search.emarefa.net/detail/BIM-465914
American Medical Association (AMA)
Ercal, Gunes. More Benefits of Adding Sparse Random Links to Wireless Networks : Yet Another Case for Hybrid Networks. International Journal of Distributed Sensor Networks. 2012. Vol. 2012, no. 2012, pp.1-12.
https://search.emarefa.net/detail/BIM-465914
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-465914