索引词 |
| 无线网络,近似算法,广播算法,无线调度。 |
介绍 |
| 全网广播是在无线网络中,一个基本操作的信息需要从源头传播到所有的网络中其他节点。可能会有多个消息来自多个源的播放。鉴于多次反射无线网络的关键应用程序包括提示对象检测用传感器、低延迟广播方案的设计必须满足严格的端到端延迟的要求更高级的应用程序。无线网络的干扰是一个基本限制因素。当两个或多个节点发送消息到一个共同的邻居同时,普通节点不会接收这些消息。在这种情况下,我们说碰撞发生在普通节点。干扰范围可能比传输更大的范围,在这种情况下,一个节点可能不会收到消息从发射机干扰范围内如果是另一个节点发送消息。近似算法是算法用于寻找优化问题的近似解。近似算法是常与np难度问题,因为它不太可能能有有效的多项式时间的算法解决np难问题。最早的广播机制提出了文学是洪水[1],[2],网络中的每个节点传递一个消息给它的邻国在收到它。 Although flooding is extremely simple and easy to implement, Ni et al. [3] show that flooding can be very costly and can lead to serious redundancy, bandwidth contention, and collision: a situation known as broadcast storm. |
| 答:我们的贡献 |
| 我们给所有和所有广播算法问题。在所有广播,源节点发送一个消息到所有其他节点的网络。在所有每个节点广播发送自己的消息到所有其他节点。甚至所有广播问题是np完全[4]。对于这两个问题,我们开发近似算法,改善以前的结果。对于所有广播问题,我们提出一个简单的近似算法,实现12-approximate解决方案,从而提高近似16的保证。我们的算法是基于算法的甘地等。[4],包含以下两个想法导致改进:1)处理节点贪婪地不增加订单数量的接收器,和2)允许节点传输不止一次。所有广播问题我们提出两种算法(称为CDA和ICDA)近似的保证20到34岁的分别,从而提高近似27的保证。ICDA的所有节点都将参与尽可能早地传输。我们的算法实现37%改善端到端延时超过现有的方案。 |
相关的工作 |
| 提出了几种技术在无线网络广播。为了减少广播冗余和论点,他们利用节点的邻居信息,确定是否一个特定的节点需要传输消息[5],[6]。有一些工作在latency-constrained广播有线网络[7]和一些结果确实存在的无线网络模型本质上是和我们的一样。这个结果并不直接延伸到ad hoc网络建模的限制类几何图形称为磁盘图表。甘地等。[4]表明,减少广播在无线网络延迟是np完备性,然后提出一个近似算法,所有广播。 |
| 答:网络模型 |
| 当干扰范围和传播范围是相同的,无线网络可以建模为一个单位圆盘图(UDG), G (V, E)。V的节点是嵌入在平面上。u单位每个节点传输范围。让uj;vj表示u和v之间的欧几里得距离我们假设时间是离散的。我们假设每个消息传输占用单位时间槽:即。一个成功传输的延迟是一个单位的时间。我们说有一个碰撞节点w,如果w听到消息同时从两个发射器。在这种情况下,我们还说,两个传输干扰w。一个节点w接收一条消息碰撞自由iff w听到消息没有任何碰撞。 |
| b .问题陈述: |
| 磁盘图G = (V, E)和一组消息M = (m1;平方米;。;mn)。一组用于这些消息的来源作为来源:(sj | sj的来源消息j)。一个节点可以发送消息j之后才收到消息碰撞自由。安排指定为每个消息j和我,每个节点的时间节点我收到消息j碰撞自由的时间它传送消息j。如果一个节点没有传输消息的传输时间,消息是0。播放进度的延迟是第一次,每个节点接收所有消息。传输的数量的总数乘以每个节点传递任何信息。我们的目标是计算的进度延迟最小化。使用的所有和many-to-all广播。所有广播是操作中有一个源节点年代消息发送所有其他节点。 In all-to-all broadcasting each node v has its own message m to send all other nodes. |
所有广播算法 |
| 该算法需要输入和一个源节点s。如果一个节点u是父节点的节点w然后u负责将消息传送到w没有任何碰撞。这个算法会导致显著提高近似保证是1。贪婪的方式处理节点2。允许一个节点传输不止一次。它会导致保证接收器节点将收到消息碰撞自由通过克服广播问题。该算法首先构造BFS树。在BFS非递增的顺序节点是主节点。孩子们主节点的辅助节点。在所有广播传输计划在两个阶段。在阶段1中,该算法只安排传输节点集合X中包含所有主要和非叶节点辅助节点的树。 In Phase 2, transmissions are scheduled to send the message to all other nodes. In Phase 1, nodes are considered one level at a time starting from Level 0. Only those primary nodes that have a child will transmit the message in this phase. The Primary nodes that doesn’t have child will transmit in the phase 2. |
所有广播算法 |
| 所有广播,网络中的每个节点将消息传送到网络中其他节点。克服问题我们改变的价值近似比20到34岁使用收集和分布式算法(CDA)和交叉收集和分发算法(ICDA)。的传输开销,我们的算法显示CDA和ICDA一直都使用少的传输比现有的一个。 |
| 答:收集和分配算法(CDA) |
| 该算法包括两个阶段。在第一阶段,源节点收集所有执行上行传输的数据包。在阶段2中,所有n源节点广播数据包通过下行传输所有其他节点。 |
| 阶段1。源节点收集所有消息。算法如下:首先构造一个石树从s,并以非递减顺序排序消息级别的石树。即,接近年代出现的消息首先在分类列表中。让我们假设消息j是j消息的顺序。集合的延迟算法最多减少。 |
| 阶段2。我们构建一个广播树。接下来,我们描述传输调度算法。算法的甘地等。[4],根节点收集所有消息和执行所有(每个消息广播。根节点需要等到前一个消息到达前的水平开始广播为另一个消息,以确保没有碰撞的算法。在这个算法中,我们找到一个时间表由顶点着色,确保所有节点有相同的颜色可以广播消息没有碰撞,并显示17个颜色就足以获得无碰撞的时间表。然后计算广播树让k1, k2是颜色的数量。我们定义了一个superstep k时段。在每个superstep,第一k1槽为调度从初选,剩下的k2槽将为辅助。每个主要颜色我只允许在第i个传输superstep主槽的槽。 Each secondary receiving a packet in a superstep transmits the received packet in the corresponding secondary slot in the same superstep. |
| b .交叉用来收集和分配算法(ICDA) |
| 在算法的早期阶段,直到年代收到所有的信息并开始传播,大多数节点处于空闲状态,从而显著增加广播时间。因此它描述了一种算法中所有节点尽快参与广播播出时间最小化。m v节点接收一条消息转发来自其后代x的广播树和继电器母公司将消息传递到根节点。的孩子v时也可以接收消息广播。使用广播树构造成在CDA,我们计划为每个节点传输如下:在CDA,我们定义了一个superstep而是一种稍微不同的方式。在每个superstep,每个节点最多传递一条消息(向上或向下)。而不是完成所有上行传输首先,我们将在每个superstep向上或向下传输与偏好向上传输。 |
| c。结果所有广播 |
| 虽然我们尝试了不同的设置,我们只报告一组代表结果在本节的其余部分。在图2中,我们呈现近似的平均比率不同节点的数量在一个固定大小的平方1000 _ 1000。我们的算法12-40百分比始终优于现有的方案。具体地说,在400 -节点的情况下,近似算法的比例平均为1.74,小于21%左右的GPM(2.22)和PBS(小于2.21)和40%的EBS (2.92)。近似比我们的计划略有上升,但在现有的性能改进方案是相似或更大。 |
| 在图3中,我们目前的平均价值实际延迟广播算法以及石树的高度(即。,下界)。广场它不同节点的数量和大小,这样的平均数量的邻居保持相似。持续观察,该算法优于现有方案11-37百分比。d .的结果所有广播 |
| 在图4中,我们目前的平均近似比所有广播方案(CDA和ICDA), MSB和广场IGA,不同节点的数量和大小。在实践中观察到的性能CDA和ICDA比分析绑定(20 - 34)。CDA表现良好时,网络规模小但是,CDA和MSB变成小之间的性能差异较大的网络。 |
结论 |
| 因此一个近似算法在无线网络实现广播。ONE-TOALL广播给12-approximate算法解的算法所有广播给近似20到34岁的比率。但它非常大的多次反射网络是不够的,所以在未来可以实现很大的多次反射网络的高效的方式减少延迟和无碰撞,找到无线网络的延迟时间。 |
数据乍一看 |
|
|
|
引用 |
- c . Ho k . Obraczka g . Tsudik, k . Viswanath”洪水可靠多播的种特设网络,“Proc。第三国际研讨会上离散方法和算法为移动计算和通讯,64 - 71年,1999页。
- j . Jetcheva y胡、d·麦克斯维尔和d·约翰逊,”一个简单的协议在移动Ad Hoc网络多播和广播,“互联网IETF草案,2001年7月。
- S.-Y。倪,研究。曾,Y.-S。陈,j。许凤,“移动Ad Hoc网络广播风暴问题,“Proc。ACM和IEEE MobiCom, 151 - 162年,1999页。
- r·甘地,a米希拉,美国的高“最小化广播在特设网络延迟和冗余,“IEEE / ACM反式。网络、16卷,没有。4,第851 - 840页,2008年8月。
- w·彭和x,“AHBP:一个有效的移动Adhoc网络广播协议网络,”j .科技、16卷,第125 - 114页,2000年。
- j . Sucec和i Marsic”,一个高效的分布式移动Adhoc网络全网广播算法网络”技术报告,罗格斯大学,2000。
|
菜单
