Ad hoc networks是由一群能彼此互相通訊的無線裝置所組成的，在這種環境下沒有無線基地台來協助訊息傳送，無線裝置必須透過多跳(multi-hop)的方法才能傳送訊息。然而這些無線裝置通常是依賴電池來提供所需要的電力，因此無線裝置可能進入PS(Power-saving)模式來節省電力的消耗。以往Quorum-based asynchronous PS協定是設計去協調兩個無線裝置，即使它們是非同步的清醒次序，也能有機會同時清醒，以便進行訊息傳送。然而Quorum-based asynchronous PS協定只能確保兩個無線裝置能夠同時清醒。這樣對於群播訊息需要多個接收者同時清醒，它將是不能保證。當要進行群播訊息時可能會有部份的接收者是處於PS模式狀態，造成訊息可能需要重新傳送，因而加深電力的消耗，且失去了群播的好處。故在本論文中，我們提出一個新的非同步PS協定來解決非同步ad hoc networks的群播問題，稱CRT-MAC PS協定。我們並且導入difference m-pair的特性來確保m個不同的清醒次序有交集存在，這樣m個無線裝置依據滿足difference m-pair特性的清醒次序來清醒，將能有機會同時清醒。CRT-MAC PS協定是使用中國餘式定理的概念來產生m個無線裝置的清醒次序，依據中國餘式定理的所產生出來的清醒次序將能滿足difference m-pair的特性。這樣當要傳送群播訊息給m個無線裝置時，每個無線裝置會從滿足difference m-pair特性的清醒次序中選擇一個新的清醒次序來清醒，最後m個無線裝置將能同時清醒，以利群播訊息的傳送。

The asynchronous PS (Power-Saving) protocol was designed to synchronize two wireless hosts in the asynchronous ad hoc network such that those two wireless hosts can transmit an unicast message even though they have asynchronous wakeup frequencies. However, for transmitting a multicast message to more than one receiver, the protocol could not guarantee that all receivers can wake up simultaneously. It is possible that some receiver is in the PS mode when the multicast message is transmitted and then the multicast message may need to retransmit until all receivers are awake. It will increase the energy consumption and the usage of the bandwidth. In this paper, we propose a new asynchronous PS protocol, named CRT-MAC PS protocol, for the multicast transmission in the asynchronous ad hoc network. We introduce the difference m-pair property to guarantee that m different wakeup frequencies have the intersection. Thus, m wireless hosts with m different wakeup frequencies satisfying the difference m-pair property could wake up simultaneously. The CRT-MAC PS protocol utilizes the concept of Chinese Remainder Theorem to generate m wakeup frequencies which satisfy the difference m-pair property. When m wireless hosts are required to transmit the multicast message, each wireless hosts will choose a new wakeup frequency generated by the concept of Chinese Remainder Theorem. Eventually, these m wireless hosts will wake up simultaneously and receive the multicast message.

Contents

誌謝..................................................i
摘要.................................................ii
Abstract............................................iii
Contents..............................................v
List of Tables.......................................vi
List of Figures.....................................vii
1. Introduction.......................................1
2. Related works and problem statement................5
2.1 IEEE 802.11 PS mode in ad hoc networks.........5
2.2 A quorum-based asynchronous PS protocol........6
2.3 Difference pair................................8
2.4 Problem statement.............................10
3. The CRT-MAC PS Protocol...........................11
3.1 Difference m-pair.............................11
3.2 Chinese Remainder Theorem.....................12
3.3 CRT-MAC PS protocol...........................13
4. Simulation setting and results....................17
5. Conclusion........................................19
References...........................................20

[1]LAN MAN Standard Committee of the IEEE Computer Society, IEEE Std 802.11-1999, “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications,” IEEE, 1999.
[2]QualNet, http://www.scalable-networks.com/.
[3]C.M. Chao and J.P. Sheu, “An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks,” IEEE Transactions On Mobile Computing, vol. 5, 2006.
[4]L.M. Feeney and M. Nilsson, “Investigating the Energy Consumption of Wireless Network Interface in an Ad Hoc Networking Environment,” IEEE INFOCOM, pp.1548-1557, 2001.
[5]P. Hurni, T. Braun, and L.M. Feeney, “Simulation and Evaluation of Unsynchronized Power Saving Mechanisms in Wireless Ad Hoc Networks,” WWIC, pp. 311-324, 2006.
[6]M. Hall Jr., Combinatorial Theory. John Wiley & Sons, 1986.
[7]J.R. Jiang, Y.C. Tseng, C.S. Hsu, and T.H. Lai, “Quorum-Based Asynchronous Power-Saving Protocols for IEEE 802.11 Ad Hoc Networks,” ACM Journal on Mobile Networks and Applications, 2005.
[8]X. Jiang, J. Polastre, and D. Culler, “Perpetual environmentally powered sensor networks,” IEEE SPOTS, 2005.
[9]C.M. Lin, G.M. Chiu and C.H. Cho, “A New Quorum-Based Scheme for Managing Replicated Data in Distributed Systems,” IEEE Transactions On Computers, vol. 51, 2002.
[10]W.S. Luk and T.T. Huang, “Two New Quorum Based Algorithms for Distributed Mutual Exclusion,” Proc. Int’l Conf. Distributed Computing Systems, pp.100-106, 1997.
[11]M. Maekawa, “A √N Algorithm for Mutual Exclusion in Decentralized Systems,” ACM Trans. Comput. Syst., pp. 145-159, 1985.
[12]C.E. Perkins, “Ad Hoc Networking,” Addison Wesley, 2001.
[13]J. So and N.H. Vaidya, “A Multi-Channel MAC Protocol for Ad Hoc Wireless Networks,” Proc. ACM Mobihoc’04, 2004.
[14]Y.C. Tseng, C.S. Hsu, and T.Y. Hsieh, “Power-Saving Protocols for IEEE 802.11-Based Multi-Hop Ad Hoc Networks,” IEEE INFOCOM, 2002.
[15]C.H. Wu, J.H. Hong and C.W. Wu, “RSA Cryptosystem Design Based on the Chinese Remainder Theorem,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 391-395, 2001.