隨意式網路下透過相對補集理論提出一個改良連通支配集演算法

An Improved Connected Dominating Set Algorithm by Relative Complement Set Theory in Ad Hoc Network

林信志(XIN-ZHI LIN)

指導教授 ： 江茂綸

朝陽科技大學/資訊學院/資訊與通訊系/碩士(2017年)

摘要

隨著行動裝置的蓬勃發展，使用者可以隨時擁有透過行動裝置來獲取網路的機動性及便利性，其中又以無基礎設施的隨意式網路(Ad-Hoc)拓樸為最為風行之應用。其無線式隨意式網路資料的傳送主要是透過點對點(Peer-to-peer)互相通訊或是轉送技術來達成，完全不需要任何有線網路的架構或設備的支援，不但可隨時改變其網路拓樸型態，同時也沒有移動方向或範圍的限制。因此，這類型的架構適合應用於緊急救災及軍事用途上，是屬於比較俱有彈性之網路架構。
然而，在隨意式網路中，亦有一些問題存在，例如頻寬與傳輸範圍的限制、節點的處理能力及電池功率等。由於上述問題的限制，如何在隨意式網路中作最有效率的繞徑，來減少節點在儲存路由表格(routing table)及選擇路徑傳輸封包所耗損的電力及頻寬，將是很重要的議題。
基於上述原因，透過連通支配及作為虛擬骨幹運用於Ad-Hoc無線網路已被提出。然而，由於節點分佈狀態不佳，過去所提出的演算法不能有效地降低CDS的數量。因此，我們提出了Relative Complement Sufferage CDS(RCS-CDS)協議，透過相對補集理論來建構出最小的CDS。

關鍵字

相對補集 ； Ad-Hoc無線網路 ； 路由演算法 ； 連通支配集

並列摘要

With the rapid development of mobile devices, users can always obtain the mobility and convenience of the network by using the mobile devices. One of the popular network structures named Ad-Hoc is used to non-infrastructure topology. When the network information is transmission in the Ad-Hoc, it mainly depends on the peer-to-peer communication or the forwarding technology without any wired network architecture or devices supported. From this point, the network structure can change easily in any time and no limit of the movement direction or the range. Therefore, this type of architecture is suitable for emergency relief and military, because of its flexible network architecture.
However, in the Ad-Hoc network, there are some issues in the Ad-Hoc network need to be considered, such as bandwidth, transmission range restrictions, processing power and battery power. As a result of the above restrictions, how to reduce the power and bandwidth consumption in Ad-Hoc network by using efficient routing that is very important issue.
Based on reason above, the Connected Dominating Set (CDS) is proposed and used as a virtual backbone in the Ad-Hoc wireless network. However, the previous algorithm cannot reduce the size of CDS effectively due to poor node configuration. Therefore, a Relative Complement Sufferage CDS (RCS-CDS) protocol is proposed to construct the minimum size of CDS by using the relative complement theory.

並列關鍵字

Relative Complement ； Ad-Hoc Wireless Network ； Routing Algorithm ； Connected Domination Set

參考文獻

[1]林靖洋，“隨意無線網路中虛擬骨幹的局部維護機制”，碩士論文，國立中山大學電機工程學系，高雄，2013。

[2]國家教育研究院, http://terms.naer.edu.tw/detail/1279653/

[3]賈坤芳、江茂綸、陳俊榮，“用區域演算法將ad hoc 無線網路下之Connected Dominating Set 最小化”，全國計算機會議，2005。

[4]陳俊榮，“Ad Hoc無線網路中利用ID重置技術建構最小省電Connected Dominating Set的區域演算法”，碩士論文，國立中興大學資訊科學研究所，臺中，2006。

[5]M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A Review of Routing Protocols for Mobile Ad hoc Networks,” Ad hoc networks, January 2004, Vol. 2, No. 1, pp. 1-22.