期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2012
卷号：2012
DOI：10.1155/2012/361621
出版社：Hindawi Publishing Corporation
摘要：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 𝑘 controlling sparsity,
any node has a probability of 1/𝑘2𝑛𝑟2 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
𝐺1, and alternatively we consider a sparser model 𝐺2 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 𝐺1 is 𝑂(𝑘
