对中小型无线网络的线性研究结果.doc

对中小型无线网络的线性研究结果 A. Eslami, Student Member, IEEE, M. Nekoui, Student Member, IEEE, and H. Pishro-Nik, Member, IEEE 摘要：分析中小型无线网络时无线领域中的基础问题。目前，由于在大型无线网络领域涌现出大量的文献，我们对于这些网络渐进的行为有了公正的解读。 然而，在现实生活中，我们不得不面对中小型网络，因为其渐进结果不再有效。当网络节点数少于几百个时，我们把网络称为中小型网络。本文，我们研究了由几何随机图几何随机图 关键词：中小型无线网络 阈值现象 MAC层容量 随机集合图形 简介 目前，在不同性质的大型随机网络的渐进分析领域已经存在大量的文献资料[1]-[14]。然而，在现实中，我们不得不面对只有有限个节点的中小型网络。正如前面作者提到的，在分析这些网络时，渐进分析方法不再凑效。[15],[16]。实际上，渐进分析方法所使用的方法和近似可以大大简化分析，得出简单的结果和封闭的网络属性公式。然而，一般情况下，许多这些的技巧并不适用于小型网络。在这，我们研究了一种可大量用于分析随机网络的模型：随机几何图形。在随机几何图形中，顶点按照一种特定的概率随机分布，任何两个顶点的距离不会超过一个特定的界限。 我们首先研究了用随机几何图形建模的中小型网络中单向性的阈值现象。一个单向图形属性是这样一种图形，如果图形H满足这种属性，那么在同一个顶点集中的每个图形G通过加边线都能获得图形Ｈ的图形同样满足这种属性。需要指出许多图的属性比如连通性，都拥有一个特定大小的子图，或者是具有一个最低程度的单向属性。使单向性这么有趣的是在一个大型随机图形中，在一个相对较短的通信半径间隔，单向性可以从接近０的数字跳变到接近１。这个间隔的长度，通常叫做阈值宽度，在渗流理论，统计物理学，聚合理论和计算机科学中，经济学和政治学一些相关的问题都有着密切的研究。在［１］，［４］－［７］中随机集合图形中的阈值的渐进行为有着很好的研究，其中有些利用上界导出了单向性的宽度。在这，我们的目标是研究当一个图形只有有限的节点时的阈值现象。在这篇论文中，我们首先找到在有限一维的随机集合图形中的单向性的阈值上限。其他随机网络模型，如有着泊松节点分布和不可靠传感网格也会当做特例有所涉及。需要指出，以前关于中小型网络的研究局限于特定的属性，比如覆盖和连通性（查看例子［１５］－［２０］）。然而，我们的方法是综合的，导致约束，对所有的单向性适用。 然后我们接着研究了中小型网络的非单向特性——ＭＡＣ层的容量。在通信半径为０时，ＭＡＣ层地容量也为０，ＭＡＣ层地容量随着ｒ的增长而增长，当到达某个点时，增加ｒ会导致更多的干扰，因此，随着ｒ的增长ＭＡＣ层地容量也减小。所以，ＭＡＣ层地容量不是单向的。对不同模型的容量问题已经经过了广泛的研究（查阅例子［９］，［１４］）。然而，以前几乎所有的研究结果都是渐进的因为他们考虑都是大型网络。在这篇论文的第二部分，我们研究了随机线路网的ＭＡＣ层容量。在点对点模式的无线网络渐进的ＭＡＣ层容量在［２１］中有研究。在［２１］中ＭＡＣ层的容量被定义为在ＭＡＣ层中同时传输的最大数量。然而，在［２１］获得的渐进性的结果在分析中小型网络时不再准确。在这，我们得到了ＭＡＣ层容量的上下界。而且，我们提供了一种算法，它可以准确计算出连接了一组活动连接的ＭＡＣ层容量。该算法以线性时间运行，然而计算一般二维的情况的ＭＡＣ层的容量问题在本文所考虑的模型被证明是ＮＰ问题［２２］。我们的模拟表明，我们的边界算法是对真实数据的一个很好的评估。 本文的其余部分是按以下来安排的。在第二部分，我们推导出一维中小型网络的阈值宽度的上界。随后，在第三部分，我们分析了随机线路网的ＭＡＣ层容量。在第四部分结束全文。 ２．中小型线路网的阈值现象 　　 　　　在这部分我们推导了中小型线路网的阈值宽度的上界。考虑有ｎ个点均匀独立的分布在ｄ维单元立方体［０，１］ｄ中。给定一个确定的ｒ＞０，如果两点之间的欧几里得距离不超过ｒ，它们之间是连通的。这种图形被叫做几何随机图，这个图形是满足每个单向性的完全图，然后，01,让r（n，）=inf{r0:Pr{G(n,r,f(u))拥有属性A}。我们定义阈值宽度A为,当01/2时，[4]的作者证明了所有的单向图形在大型的几何随机图中都有一个尖锐的阈值。事实上，几何随机图中的阈值比伯努利随机图更加尖锐。 如果有所有的那么A的阈值属性就被认为是尖锐的，这里有如果Pr{G(n,rc,f(u))有属性A}=1/2，rc=r。然而，大多数以前的研究成功强调了阈值的渐进行为。本文，我们只考虑中小型（一维）几何随机图。事实上，维数多的几何随机图通常更难分析。我们相信研究一维的中小型几何