無線隨意與感測網路之最佳省電協定

Abstract

隨建即連網路(mobile ad hoc network，縮寫為MANET)或是無線感測網路(wireless sensor network，縮寫為WSN)是由一群大量的無線裝置所組成。由於無線裝置是通常是由電池供電，所以設計一個好的省電(或稱為電源管理)協定來延長整個網路或是個別裝置的壽命並且能夠同時維持網路連接性以及降低資料傳送時的延遲就顯得特別重要。在本篇博士論文中，我們分別針對平面式隨建即連網路(flat MANET)、叢集式隨建即連網路(cluster MANET)以及無線感測網路提出了不同的省電協定，其個別的特性詳述如下: 對平面式隨建即連網路，我們提出了一個OFAA (optimal fully adaptive and asynchronous)電源管理協定，該協定有下列特徵: (i)借助於factor-hereditary quorum space，OFAA保證任兩個相鄰的無線裝置，不論它們之間的時間誤差以及個別的排程重複區間(schedule repetition interval，縮寫為SRI)是多少，都可以在有限時間內互相發現對方。(ii)給定SRI長度，無線裝置的工作週期(duty cycle)達到理論最小值。(iii)每個無線裝置可以使用的SRI個數達到理論最大值。 (iv)OFAA的鄰居維護的時間複雜度為O(1)。(v)我們提出了一個跨層的SRI調控方法，讓每個無線裝置可以在最省電的情況下根據資料延遲需求動態地調控其SRI。 對叢集式隨建即連網路，我們提出了一個OAMA (optimal asymmetric and maximized adaptive)電源管理協定，該協定有下列特徵: (i)借助於factor-correlative coterie-plane product，OAMA保證任兩個相鄰的叢集頭(clusterhead)以及相鄰的叢集頭與叢集成員(cluster member)，不論其個別的SRI以及它們之間的排程偏移是多少，都可以在有限時間內互相發現對方。(ii)給定SRI長度，每個叢集頭與叢集成員的工作週期達到理論最小值。(iii)在最小工作週期的限制下，每個叢集頭與叢集成員可以使用的SRI個數達到理論最大值。(iv) OAMA的鄰居維護的時間複雜度為O(1)。(v)我們提出了一個跨層的SRI調控方法，讓每個叢集頭與叢集成員可以在最省電的情況下根據資料延遲需求動態地調控其SRI。 對無線感測網路，我們提出了一個最佳及最大可調控度的電源管理協定稱為Green-MAC，該協定有下列特徵: (i)借助於一般化的中國餘式定理(generalized Chinese remainder theorem)，Green-MAC保證任兩個相鄰區域的感測器，不論其個別的循環長度(cycle length)以及它們之間的排程偏移是多少，都可以在有限時間內同時醒來。(ii)給定循環長度，每個感測器的ATF-ratio(一個循環中處於醒來時段的比例)達到理論最小值。(iii)在最小ATF-ratio的限制下，每個感測器可以使用的ATF-ratio個數達到理論最大值。(iv)我們為Green-MAC提出了一個ATF-ratio調控方法，在每個感測器可以在最省電的情況下讓event-to-sink的延遲需求被滿足機率很高。 透過理論分析以及大規模的模擬實驗顯示我們所提出的省電協定，包含OFAA、OAMA以及Green-MAC，在效能上可以大幅勝過相關領域裡的現有頂尖研究。

A mobile ad hoc network (MANET) or a wireless sensor network (WSN) typically consist of a large number of wireless devices. Since wireless devices are often battery-powered, it is vital to design good power saving (or called power management) protocols to prolong the lifetimes of a whole network and individual wireless devices, while maintaining the network connectivity and keeping the data transmission delay relatively low. In this dissertation, we propose three different optimal power saving protocols for flat MANETs, clustered MANETs, and WSNs, respectively, the features of which are presented as follows. For flat MANETs, we propose an OFAA (optimal fully adaptive and asynchronous) power management protocol, which has the following attractive features. (i) By means of factor-hereditary quorum space, OFAA guarantees that two neighboring stations can discover each other in bounded time regardless of their clock difference and individual schedule repetition intervals (SRIs). (ii) Given the length of SRI, the duty cycle of a station reaches the theoretical minimum. (iii) The number of tunable SRIs of every station reaches the theoretical maximum. (iv) The time complexity of OFAA neighbor maintenance is O(1). (v) A cross-layer SRI adjustment scheme is proposed such that a station can adaptively tune the values of SRI to maximize energy conservation according to flow timeliness requirements. For clustered MANETs, we propose an OAMA (optimal asymmetric and maximized adaptive) power management protocol, which has the following attractive features. (i) Given the length of SRI, the duty cycles of both clusterheads and members reach the theoretical minimum. (ii)Under the minimum duty cycle constraints, the numbers of tunable SRIs for both clusterheads and members reach the theoretical maximum. (iii) By means of factor-correlative coterie-plane product, OAMA guarantees bounded-time neighbor discovery between the clusterhead and its member, and between all clusterheads, regardless of stations’ individual SRIs and the schedule offset between neighboring stations. (iv) The time complexity of OAMA neighbor maintenance is O(1). (v) OAMA adopts a cross-layer SRI adjustment scheme such that stations can adaptivelytune the values of SRI to maximize energy conservation according to flow timeliness requirements. For a WSN, we propose an optimal and maximized configurable power saving protocol, named Green-MAC, which has the following attractive features. (i) By using the generalized Chinese remainder theorem, Green-MAC guarantees that any two sensors in the neighboring coronas can simultaneously wake up in bounded time regardless of their schedule offset as well as their respective cycle lengths. (ii) Given the cycle length, the ATF-ratio (i.e. the fraction of awake time frames in a cycle) of each sensor reaches the theoretical minimum. (iii) Under the minimum ATFratio constraints, the number of configurable ATF-ratios of each sensor reaches the theoretical maximum. (iv) An ATF-ratio configuration scheme is proposed for Green-MAC such that the power consumption of a WSN can be minimized while the worst event-to-sink delay requirement can be fulfilled with high probability. Through both theoretical analyses and extensive simulations, we demonstrate that our proposed power saving protocols, including OFAA, OAMA, and Green-MAC, significantly outperform related state-of-the-arts in flat MANETs, clustered MANETs, and WSNs, respectively.