應用數學規劃在大型隨意網路上多重通訊協定之研究

為了有效管理封包之傳遞，近年來在大型隨意網路(MANET)上之多重通訊協定(multicast protocols)主要採取兩階層架構(two-tier infrastructures)之設計。但是這些多重通訊協定有以下三個缺點。第一，它們選取有較多相鄰通訊點之通訊點作為主幹通訊點(backbone hosts)來代理封包的遞送。此種選取方式易造成大量封包集中在這些主幹通訊點而形成網路瓶頸。第二，它們在選取主幹通訊點時未考量其移動性，因此易造成大量封包之遺失。第三，它們未能提供不同等級傳輸服務品質(Quality-of-Service)之功能。為滿足多媒體或其它有及時性需求之應用程式，多重通訊協定必須具備此功能。本論文之目的在於發展一套適用於大型隨意網路上之兩階層架構多重通訊協定。為了避免上述三項缺點，此新協定有以下五個設計目標。這五個設計目標同時也是目前在大型隨意網路上發展多重通訊協定的主要挑戰工作。 (1)減少控制封包(control packets)數目及避免封包在網路上無限制地濫送 (flooding)。 (2)減少網路壅塞。 (3)縮短多重通訊路徑。 (4)選擇移動性較低之主幹通訊點。 (5)提供不同等級傳輸服務品質之功能。為了建立兩階層架構，我們首先必須挑選主幹通訊點。我們嘗試將此問題以數學規劃來表示。數學規劃是一種數學模式且已被證明非常適用於解決在已知限制條件(constraints)下對有限資源做最佳配置(optimal allocation)之問題。上述五個設計目標將表成數學規劃之目標函數(objective functions)與限制條件。然後，藉由解出數學規劃之一組有效解(feasible solution)，主幹通訊點便可決定。我們將運用這些主幹通訊點來完成一套符合我們需要的多重通訊協定。以下是此多重通訊協定所具備之功能。 (1)建立與管理兩階層架構。 (2)建立多重通訊路徑。 (3)管理多重通訊群組之動態關係(dynamic group membership)。 (4)因應通訊點之移動，隨時更新多重通訊路徑與調整兩階層架構。 (5)提供一個進出控管機制(admission control mechanism)以滿足多重通訊應用程式傳輸服務品質之需求。我們所設計之多重通訊協定，不僅能建立一個具有較少控制封包與較少遺失封包之穩定兩階層架構，而且能建立較短的多重通訊路徑與滿足多重通訊應用程式傳輸頻寬(bandwidth)之需求。

關鍵字

隨意網路；數學規劃；多重通訊；最佳化

並列摘要

Recent multicast protocols for large-scale mobile ad hoc networks (MANETs) adopted two-tier infrastructures to achieve effective flooding schemes. They have three disadvantages. First, hosts with a large number of neighbors were selected as backbone hosts (BHs) for forwarding packets. It is very likely that these BHs will become traffic concentrations or bottlenecks of the networks. Second, they suffered from more lost packets because they did not consider host mobility in selecting BHs. Third, they did not provide quality-of-service (QoS) function. A multicast protocol is desired to provide different levels of QoS for multimedia and real-time applications. In this dissertation, we aim to develop a new two-tier multicast protocol for a large-scale MANET. In order to avoid the above disadvantages, the new multicast protocol has the following five design goals, which are the main challenges to providing multicast services in MANETs. (1)To reduce the number of control packets and avoid flooding over the entire network. (2)To lower traffic concentrations and bottlenecks of the network. (3)To shorten multicast routes. (4)To select stable BHs. (5)To provide the QoS function. To establish a two-tier infrastructure, BHs will be selected first. We attempt to formulate the problem of selecting BHs by mathematical programming (MP), which is a mathematical model that has been proved useful for optimal allocation of limited resources to known activities under some constraints. The five design goals are merged into the formulated MP as objective functions and constraints. Then BHs will be determined by solving the formulated MP for a feasible solution. Finally, the new multicast protocol will be developed based on the selected BHs. The new multicast protocol is responsible for the following tasks. (1)Establish and maintain the infrastructure. (2)Construct multicast routes. (3)Manage dynamic group membership. (4)Update multicast routes and adjust the infrastructure in response to host movements. (5)Provide an admission control mechanism. The new multicast protocol not only establishes a stable two-tier infrastructure with fewer control packets transmitted and fewer data packets lost, but also constructs shorter multicast routes and meets the bandwidth requirements of multicast applications.

並列關鍵字

Ad hoc network ； mathematical programming ； multicast ； optimization

參考文獻

[1] C. M. Cordeiro, H. Gossain, and D. P. Agrawal, “Multicast over wireless mobile ad-hoc networks: present and future directions,” IEEE Network, Special Issue on Multicasting: An Enabling Technology, January/February, pp. 52-59, 2003.

[2] W. L. Winston, Introduction to Mathematical Programming: Applications and Algorithms, PWS-Kent: Boston, 1991.

[3] H. Karloff, Linear Programming, Birkhauser: Boston, 1991.

[4] L. A. Wolsey, Integer Programming, J. Wiley: New York, 1998.

[5] G. B. Dantzig, “Programming of interdependent activities: II. mathematical model,” Econometrica, vol. 17, pp. 200-211, 1949.

國際替代計量

應用數學規劃在大型隨意網路上多重通訊協定之研究

全文下載

主題瀏覽