移動性Ad Hoc 網路之低能耗群播路由演算法研究

Abstract

移動性的Ad Hoc網路使用無線傳播，是一個不需事先決定網路拓樸設計的網路。這種網路架構的特性使得它可以被快速的部署，並且不需依賴已存的基礎建設。值得注意的是在這顯著的特徵下，它適合使用在設計階段無法預測的網路架構的應用。 然而，在設計移動性的Ad Hoc網路存在很多關鍵的挑戰需要被解決。其中三個主要的挑戰是: 1) 缺乏集中式管理, 2) 節點的自主移動, 3) 所有通訊透過無線媒介傳播。 本篇論文我們著重在探討當每個節點受限於有限的電力資源，且整個路由的路徑是由每個自主移動的節點所組成的情況下，要如何以低能耗的路由決策，成功傳送資料給群播成員，在會因為節點移動而導致傳輸中斷，而需要重新作路由決策的網路拓樸。 不同於傳統設計的單層結構，我們同時考慮在有效的傳送半徑範圍內（網路連接性，屬實體層）以及群播樹的建立（路由功能，屬網路層），來做出低能耗的路由決策。我們將此問題設計成最佳化的數學模型，並且採用拉格蘭日鬆弛法（Lagrangian relaxation）為基礎的方法來處理此複雜的問題。

The Mobile Ad Hoc Network (MANET) is an emerging network topology based on a radio propagation model. The network topology, which is neither fixed nor predetermined, can be rapidly deployed and does not need to rely on a pre-existing infrastructure. It is noteworthy that this salient feature makes it suitable for the network operations that, by their nature, are unpredictable during the design stage. However, a lot of critical challenges in the design and operation of MANET need to be solved. The three main challenges come from: 1) the lack of a centralized entity, 2) the possibility of platform movements, 3) the fact that all the communication is carried over the wireless medium. The issues we address here are 1) a node operates on limited battery resources, and 2) multi-hop routing paths are used over constantly changing network environments due to node mobility. Hence, efficient utilization of routing packets and immediate recovery of route breaks are critical in routing and multicasting protocols in MANET. Our approach to energy-efficient communication departs from the traditional layered structure in that we jointly address the issues of transmitted power levels (a network connectivity function, related to the Physical layer) and multicast tree formulation (a routing function, associated with the Network layer). We model the problem as a linear integer mathematical programming problem. In addition, we propose a set of heuristic solution procedures based on Lagrangian relaxation methods to solve the complicated problem.