关键字 |
自组织网络,蜂窝网络,GSM,混合网络,整数线性规划。 |
我的介绍。 |
蜂窝网络通常由固定基站(BSs)组成的有线骨干网组成。移动用户订阅BS并直接与它通信。蜂窝网络的主要优点是蜂窝覆盖范围大。然而,它们通常提供非常有限的带宽(例如,3G网络支持的带宽为384 kb/s至2 Mb/s),当同一小区中有大量用户时,BSs是潜在的性能瓶颈。为了克服蜂窝网络的局限性,人们对自组织网络与蜂窝网络的集成进行了广泛的研究。在无线自组织网络中,移动节点在没有标题基础设施支持的情况下立即形成网络。每个移动节点都可以充当网络中的路由器,通过多跳无线链路为其他节点中继数据包。因此,在蜂窝自组织混合网络中,可以使用移动主机向其他节点转发报文,以增加基站的覆盖或避免盲点[1]、[2]。它们还可以将拥塞单元内的流量重定向到邻近的非拥塞单元[3],[4]。此外,当BSs在ad hoc模式和蜂窝模式[5]之间切换时,或者当移动用户体验到良好的信道质量(称为代理)为其他节点中继数据包时,系统吞吐量可以增加。 A number of hybrid architectures have been proposed to use “multicast” to send packets to multiple receivers [8]– [10].Multicast is an efficient mechanism for point (or multipoint) to multipoint communication, which has been widely used in both wired and wireless networks. It utilizes a tree or mesh data delivery structure to reduce identical packets on the network links and preserve link bandwidth. By exploiting the benefits of multicasting among mobile users (i.e., ad hoc multicast), these architectures can enhance network performance, especially for applications with heterogeneous receivers. Our paper, on the other hand, targets at the scenarios in which BSs manage multiple groups simultaneously. We consider all types of groups, namely 1) groups solely formed by local users in one cell, 2) groups consisting of users from other cells, and 3) virtual groups implicitly formed by users receiving the same content, such as web content and streaming media. To reduce multicast traffic load on BSs, we also propose using ad hoc multicast (called “ad hoc mode”). However, due to the capacity limit of the ad hoc network, if all the groups are routed in ad hoc mode, the network may become congested, and the performance of these groups may be degraded significantly. Thus, it is critical to determine which groups should be admitted into the ad hoc network so that the work load on BSs is minimized and the utilization of the ad hoc network (without exceeding its capacity) is maximized at the same time. We refer to this problem as the “group selection problem.” |
在本文中,我们考虑了相邻节点之间的无线干扰,将群选择问题表述为多维背包问题,并提出了一个整数线性规划(ILP)公式和一个动态算法来有效地解决这个难题。我们进行仿真来评估所提出的算法。结果表明,ILP方法能给出最优解,但不适用于大容量的大型网络。另一方面,本文提出的动态算法可以获得近似最优解,更适合于在线动态系统。引言部分最后包括论文的组织结构。本文的组织结构如下:第一节介绍了有效机会路由。第2部分有助于了解相关工作的背景。第3节解释了系统建模。第4节展示了所提出的技术的性能,最后第5节总结了本文并随后给出了参考文献。 |
2相关工作 |
蜂窝网络和自组织网络之间的权衡刺激了许多努力,以将这两种类型的网络用于各种目的。一些建议侧重于增加小区覆盖或平衡小区[1]-[4]之间的负载。在[1]中,Lin和Hsu使用移动节点在BSs和移动节点之间中继数据包,以减少BSs数量,增加小区覆盖。在[2]中,开发了一个特设的全球移动通信系统(GSM)网络平台,以提高GSM覆盖和避免盲点。Wu等人提出了一种移动辅助数据转发方案,使用临时覆盖[3]将热单元中的流量引导到邻近的冷单元。在[4]中,De等人提出了一种用于蜂窝网络的称为iCAR的负载平衡方案,该方案将临时中继节点放置在战略位置,以将流量从拥塞单元中继到非拥塞单元。最近有一些关于利用AD hoc网络提高蜂窝组播性能的建议。Hauge等人提出了一种混合网络架构,以增加高带宽群组业务[8],[9]的覆盖范围。Park和Kasera开发了一种路由算法来寻找从代理到蜂窝多播接收器[10]的临时路径。与上述两种方案都是为了提高单个组播组的性能不同,本文的目标是在多个组共存的情况下使全网的性能最大化。 Our basic idea is to minimize the load of BSs by selecting appropriate multicast groups to be handled by ad hoc networks. |
|
3群体选择问题 |
3.1.问题描述 |
我们考虑一个具有BS服务于多个移动节点的单个单元。每个移动节点有两个无线网络接口,即1)HDR (high data-rate)接口和2)IEEE 802.11接口。当小区内需要一组节点(包括移动节点和基站)建立一组相互通信时,每个移动节点都连接到基站,通过点对点链路向基站发送数据,并从基站接收数据我们把这种中继方案称为蜂窝模式。或者,我们有ad hoc模式,在这种模式下,组成员可以使用802.11网络接口建立ad hoc组播树。计算单元中的移动节点可以复制和中继该组的包。这样,BS不需要中继报文(如果BS是组成员,则最多中继一次),从而节省了一定的带宽。节省的带宽量与组内用户数量(即组大小)和组数据速率成正比。 |
为了方便起见,本文只考虑所有成员都是移动节点的情况。我们的解决方案可以很容易地适应BS也是组特设模式的成员的情况。但是,当网络中有多个组同时存在时,由于ad hoc网络容量有限,可能无法容纳所有的组。在这种情况下,BS需要确定有多少组以及哪些组需要切换到ad hoc模式,以减少其带宽消耗,同时满足组的QoS要求。我们把这个问题称为群体选择问题,图1给出了一个例子。在图示的网络中,有三个组播组g1、g2和g3及其对应的树t1、t2和t3。组g1有成员{A, D, H},组g2有成员{A, B, C, E},组g3有成员{A, B, E, G}。显然,节点A很可能过载,而自组织网络可能无法容纳所有三个组。在这种情况下,BS必须选择并容纳一个或两个多播组(例如组g2),以最大限度地减少带宽,同时不违反每个移动节点的容量限制。为了解决这个问题,我们必须首先计算每个组播组的资源使用量(即带宽),然后根据它们的带宽消耗和自组织网络容量选择组的一个子集。 |
四、算法分析 |
我们的目标是最大限度地节省带宽,而不会为单个组使用太多资源,我们更喜欢需要少量带宽的大型组,即具有更高效用的组。动态算法使用效用度量作为以“贪婪”方式选择组的主要标准。 |
|
|
算法1和算法2分别显示了群组加入和离开网络时的动态算法。如图算法1所示,当一个组g加入网络时,我们首先计算组播树、所需带宽向量和效用。调用admit函数来验证ad hoc网络是否有足够的容量来接受g。如果是,g将保留带宽并切换到ad hoc模式。否则,我们尝试在ad hoc网络中找到一个合适的候选组g_,并与g交换。组g_应满足以下条件(第9行和第10行):1)g_的效用小于g, 2)如果g_释放其预留带宽,g应能被ad hoc网络接受,3)如果有多个这样的候选组,最终g_的效用最小。第9行中的swap函数检查第二个条件。在找到最佳候选组g_后,g_释放资源并切换到蜂窝模式,而组g保留带宽并使用ad hoc模式进行组播通信。同理,在算法2中,当具有ad hoc模式的分组g离开时,其预留带宽先被释放。然后,我们尝试将候选组从元胞模式切换到ad hoc模式,以减少BS的工作负载。如第5行所示,只有那些通过准入控制的组才成为候选组,最终选择效用最大的组切换到ad hoc模式。 |
A.成员动力学 |
在前面提到的动态算法中,我们基本上考虑了组成员同时加入和离开一个组的情况。实际上,成员可以单独加入或离开。为了更有用,需要扩展前面提到的动态算法来解决这个成员动态问题。例如,当一个成员加入当前处于ad hoc模式的组时,如果没有足够的容量来接纳该成员,我们有以下两个选择来遵守容量约束。如果找到候选组,则将候选组切换到蜂窝模式,释放新成员所需的带宽,并允许新成员进入ad hoc模式。否则,该组本身将切换到元胞模式。类似地,当一个成员离开一个组时,我们可以尝试将一个候选组切换到ad hoc模式,以利用释放的带宽。 |
B.朴素动态算法: |
在这里,我们提出了一个简单的算法作为参考,以评估动态算法的性能。具体工作原理如下:当有新的组加入时,如果自组织网络容量允许,则允许该组加入,并为该组预留带宽。否则,组将处于单元模式。当处于ad hoc模式的组离开时,它的带宽被简单地释放。从本质上讲,这种简单的方法是所提出的动态算法的简化版本:它既不以不同的模式交换组,也不根据组的效用来区分组。 |
诉的结论 |
本文研究了蜂窝网络和自组织网络中多播组的选择问题。我们建立了一个简单有效的模型来计算无线自组织网络中组播组的带宽需求。然后,我们将群选择问题描述为多维背包问题,并提出了ILP公式和具有多项式时间复杂度的基于效用的动态算法。此外,我们研究了动态算法如何以分布式方式实现,并讨论了节点迁移问题。最后,通过大量仿真,我们发现动态算法在大多数情况下都能获得近似最优解,并且它比ILP方法更适合在线系统 |
参考文献 |
- Y.-D。林和y - c。Hsu,“多跳蜂窝:无线通信的新架构”,载于《IEEE INFOCOM期刊》,以色列特拉维夫,2000年3月,第1273-1282页。
- G. N. Aggelou和R. Tafazolli,“关于下一代GSM蜂窝网络的中继能力”,IEEE pers.com。,第8卷,no。1,
- H.-Y。Hsieh和R. Sivakumar,“蜂窝和多跳无线网络的性能比较:定量研究”,《ACM SIGMETRICS》,2001年6月,马萨诸塞州剑桥,页。
- H. Luo, R. Ramjee, P. Sinha, L. Li和S. Lu,“UCAN:统一的蜂窝和自组织网络架构”,载于Proc. ACMMobiCom, San Diego, CA, 2003年9月,第353-367页。p. 40-47, 2001年2月。
- J. C. Park和S. K. Kasera,“使用自组织网络增强蜂窝组播性能”,发表于《IEEE WCNC程序》,2005年3月,拉斯维加斯,NV,第4卷,第2175-2181页。
- H. Luo, R. Ramjee, P. Sinha, L. Li和S. Lu,“UCAN:统一的蜂窝和自组织网络架构”,在Proc. ACMMobiCom, San Diego, CA, 2003年9月。
- D. Zhu, M. W. Mutka和Z. Cen,“通过集成蜂窝网络和自组织网络实现QoS感知无线带宽聚合(QAWBA)”,发表于《IEEE QShine期刊》,2004年10月,达拉斯,第156-163页。
- M. Hauge, a . Hafslund, F. Y. Li和O. Kure,“本地广告hocnetwork辅助的蜂窝网络上的多播服务分布”,载于Proc. Med-Hoc-Net, Bodrum,土耳其,2004年6月,第68-80页。
- M. Hauge和O. Kure,“混合3g蜂窝和ad hoc网络中的多播服务可用性”,载于芬兰奥卢IWWAN Proc, 2004年5月,第135-139页。
- S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu和L.Wei,“广域多路由的PIM架构”,IEEE/ACM Trans。Netw。,vol. 4, no. 2, pp. 153–162, Apr. 1996.
- 基于核心的树(CBT版本2)多播路由:协议规范,RFC 2189, 1997年9月。
- J. Moy,多播路由扩展到OSPF, RFC 1584, 1994年3月。
- 谢杰,R. Talpade, T. McAuley,和M. Liu,“AMRoute: Ad-Hoc组播路由协议”,ACM移动网络。:卷。7,不。6,页429-439,2002年12月。
- S.-J。Lee, W. Su和M. Gerla,“多跳无线移动网络中的按需组播路由协议”,ACM/Kluwer移动网络。达成。无线移动网络中的多点通信专刊,第7卷,第1期6页。441 - 453。
|