在無線感測網路(Wireless Sensor Networks)裡，媒體存取控制(Medium Access Control)協定的設計有幾個關鍵因素，例如節省能源、頻寬使用、吞吐量、資料延遲等等。
近幾年來，有許多研究已經提出不同的叢集式(Cluster-based)媒體存取控制協定，如LEACH是利用叢集並將叢集裡的感測節點所收集的資料聚集(Aggregation)起來加以整合，然後傳輸給基地台(Base Station)，這樣的方式能節省能源的消耗， LEACH是運用TDMA機制去做時槽的排程，時槽排程演算法會影響資料傳輸延遲與時槽(Time Slot)使用率。
在本篇論文裡，我們改良BMA(Bit-Map-Assisted)的協定，提出一個內部叢集資料通訊BMA-RR MAC協定，BMA-RR是事件驅動(Event-driven)為基礎的無線感測網路，只有當事件發生時感測節點才會收集資料，收集資料之後無線感測節點再將資料傳輸給叢集頭。本篇論文協定裡，是以Round-Robin的演算法來做資料時槽的排程，利用無線感測節點閒置期間(Idle Period)來分配更多的資料時槽(Data Slot)，以便接收或傳輸更多的資料，讓資料傳輸有更好的效率、降低資料存取的延遲。

Recent years, many researchers proposed different kinds of cluster-based MAC protocols for wireless sensors. There are several factors, e.g., energy saving, bandwidth usage, and transmission delay, affect the design of MAC protocols in wireless sensor networks. In this paper, we proposed a cluster-based energy-efficient MAC protocol named BMA-RR. The proposed MAC protocol uses Round-Robin algorithm to schedule the packets transmissions in time-slots. BMA-RR is based on event-driven data collecting scheme which gathers data when a data event is happen. After the data is collected, the sensor transmits data to its cluster head. By using Round-Robin algorithm to schedule the data transmission, the proposed BMA-RR can allocate more data slot in sending and receiving data.

摘要..........................................................iv
Abstract.......................................................v
誌謝..........................................................vi
目次.........................................................vii
表目錄.......................................................viii
圖目錄........................................................ix
第一章 簡介.....................................................1
1.1 無線感測網路................................................1
第二章 相關研究.................................................5
2.1 無線電能源消耗模型(The radio energy consumption modal).......5
2.2 媒體存取控制(MAC)協定.......................................6
2.3 無線感測網路的路由協定.......................................7
第三章 在無線感測網路上基於叢集式架構之具有效能通道存取排程..........14
3.1 叢集設定階段(Cluster Set-up Phase).........................16
3.2 穩定狀態階段(Steady-state Phase)...........................18
3.3 演算法....................................................19
3.4 電源分析...................................................22
第四章 實驗模擬與分析...........................................26
4.1 模擬架構...................................................26
4.2 模擬結果...................................................27
4.2.1 Case(1)，k=4之模擬結果....................................28
4.2.2 Case(2)，k=5之模擬結果....................................30
4.2.3 Case(3)，k=6之模擬結果....................................33
4.2.4 電源消耗與傳輸資料比較之模擬結果............................35
第五章 結論....................................................37
參考文獻........................................................38
附錄A　模擬參數的設定............................................45

表目錄
表1 資料節點的狀態-情況(1)......................................21
表2 資料節點的狀態-情況(2)......................................22
表3 各個感測節點所要傳送的資料數量...............................45

圖目錄
圖1 無線感測網路環境架構圖...........................................2
圖2 無線電能源消耗模型...............................................5
圖3 Flooding路由協定的基本架構.......................................8
圖4 SPIN路由協定的基本架構..........................................10
圖5 LEACH路由協定的叢集式基本架構....................................11
圖6 PEGASIS路由協定的鏈基礎架構.....................................12
圖7 BMA-RR的單一回合圖解............................................15
圖8 形成叢集的流程圖................................................18
圖9 叢集頭的資料時槽排程-情況(1).....................................21
圖10 叢集頭的資料時槽排程-情況(2)....................................22
圖11 單一叢集網路拓撲架構圖，N-1個感測節點以及1個叢集頭................26
圖12 Case(1)的平均延遲比較，N=11和k=4以及p的變化情況..................29
圖13 Case(1)的總電源消耗比較，N=11和k=4以及p的變化情況................29
圖14 Case(1)的傳輸量比較，N=11和k=4以及p的變化情況....................30
圖15 Case(2)的平均延遲比較，N=11和k=5以及p的變化情況..................31
圖16 Case(2)的總電源消耗比較，N=11和k=5以及p的變化情況................32
圖17 Case(2)的傳輸量比較，N=11和k=5以及p的變化情況....................32
圖18 Case(3)的平均延遲比較，N=11和k=6以及p的變化情況..................34
圖19 Case(3)的總電源消耗比較，N=11和k=6以及p的變化情況................34
圖20 Case(3)的傳輸量比較，N=11和k=6以及p的變化情況....................35
圖21 運作時間之感測節點總電源消耗與總傳輸資料量比較。(a)總電源消耗；(b)總傳輸資料量..............................................................36

[1] Jing Li, and Georgios Y. Lazarou, “A Bit-Map-Assisted Energy-Efficient MAC Scheme for Wireless Sensor Networks,” the 3rd international symposium on Information processing in sensor networks IPSN ’04, April. 2004, pp. 55-60.
[2] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 1, No. 4, Oct. 2002, pp. 660-670.
[3] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin, “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,” the 6th Annual ACM/IEEEE International Conference on Mobile Computing and Networking(MobiCom’00), August 2000, pp. 56-67.
[4] G.J Pottie, and W.J. Kaiser, “Wireless Integrated Network Sensors,” In Communications of the ACM, Vol. 43, No. 5, May 2000, pp. 51-58.
[5] Y.C. Tseng, S.Y. Ni, and E.Y. Shih, “Adaptive approaches to relieving broadcast storms in a wireless multi-hop mobile ad hoc network, ” IEEE Transactions on Computers, Vol. 52, No. 5, 2003, pp. 545-557.
[6] V. Loscri, G. Morabito, and S. Marano, “A Two-Levels Hierarchy for Low-Energy Adaptive Clustering Hierarchy(TL-LEACH),” the IEEE Vehicular Technology Conference, Vol. 3, Sept. 2005, pp. 1809-1813.
[7] S. Hedetniemi, and A. Liestman, “A survey of gossiping and broadcasting in communication networks,” Networks, Vol. 18, No. 4, 1988, pp. 319-349.
[8] Setphanie Lindsey, and Cauligi S. Raghavendra, “PEGASIS: Power-Efficient GAthering in Sensor Information Systems,” IEEE Aerospace Conference, Vol. 3, March 2002, pp. 1125-1130.
[9] Joanna Kulik, Wendi Rabiner, and Hari Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor Networks,” the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999, pp. 174-185.
[10]Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” the 33rd Annual Hawaii International Conference on System Sciences, Vol. 2, Jan. 2000, pp. 1-10.
[11]Arati Manjeshwar, and Dharma P. Agrawal, “TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks,” the 15th Parallel and Distributed Processing Symposium, April. 2001, pp. 2009-2015.
[12]Sooyeon Kim, Sang H. Son, John A. Stankovic, Shuogi Li, and Yanghee Choi, “SAFE: A Data Dissemination Protocol for Periodic Updates in Sensor Networks,” the 23rd International Conference on Distributed Computing Systems Workshops(ICDCSW ’03), May 2003, pp. 228-234.
[13]M.J. Handy, M. Haase, and D. Timmermann, “LEACH-C：Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection,” the 4th International Workshop on Mobile and Wireless Communications Network, 9-11 Sept. 2002, pp. 368-372.
[14]Siva D. Muruganathan, Daniel C. F. Ma, Rolly I. Bhasin, and Abraham O. Fapojuwo, “A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks,” IEEE Communications Magazine, Vol. 43, March. 2005, pp. S8-13.
[15] Kemei Du, Jie Wu, and Dan Zhou, “Chain-based protocols for data broadcasting and gathering in the sensor networks,” the International Parallel and Distributed Processing Symposium(IPDPS ’03), April 2003, pp. 22-26.
[16]Loren P. Clare, Gregory J. Pottie, and Jonathan R. Agre, “Self-Organizing Distributed Sensor Networks,” the International Society for Optical Engineering, Vol. 3713, Apr. 1999, pp. 229-237.
[17]Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, Vol. 40, Aug. 2002, pp. 102-114.
[18]Alec Woo, and David E. Culler, “A Transmission Control Scheme for Media Access in Sensor Networks,” the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’01), July 2001, pp. 221-235.
[19]Katayoun Sohrabi, Jay Gao, Vishal Ailawadhi, and Gregory J. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Communications, Vol. 7, No. 5, Oct. 2000, pp. 16-27.
[20]Stephanie Lindsey, Cauligi Raghavendra, and Krishna M. Sivalingam, “Data Gathering Algorithms in Sensor Networks Using Energy Metrics,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 9, September 2002, pp. 924-935.
[21]A. J. Viterbi, “CDMA: Principles of Spread Spectrum Communication,” Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995.
[22]Wei Ye, John Heidemann, and Deborah Estrin, “An Energy-Efficient MAC Protocol fro Wireless Sensor Networks,” the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 3, June 2002, pp. 1567-1576.
[23]Tijs van Dam, and Koen Langendoen, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,” the 1st international conference on Embedded networked sensor systems, November 2003, pp. 171-180.
[24]Peng Lin, Chunming Qiao, and Xin Wang, “Medium Access Control With A Dynamic Duty Cycle For Sensor Networks,” the Wireless Communications and Networking Conference, Vol. 3, March 2004, pp. 1534-1539.
[25]Shih-Hsien Yang, Hung-Wei Tseng, Eric Hsiao-Kuang Wu, and Gen-Huey Chen, “Utilization Based Duty Cycle Tuning MAC Protocol for Wireless Sensor Networks,” the Global Telecommunications Comference, Vol. 6, December 2005, pp. 3258-3262.
[26]Marcos Augusto M. Vieira, Claudionor N. Coelho. Jr., Diogenes Cecilio da Silva Junior, and Jose M. da Mata, “Survey on Wireless Sensor Network Devices,” IEEE Conference on Emerging Technologies and Factory Automation(ETFA ’03), Vol. 1, 16-19 Sept. 2003, pp. 537-544.
[27]Kemal Akkaya, and Mohamed Younis, “A Survey on Routing Protocols for Wireless Sensor Networks,” Elsevier Ad Hoc Network Journal, Vol. 3, No. 3, May 2005, pp. 325-349.
[28]Vamsi Paruchuri, Shivakumar Basavaraju, Arjan Durresi, Rajgopal Kannan, and S. S. Iyengar, “Random Asynchronous Wakeup Protocol for Sensor Networks,” the 1st International Conference on Broadband Networks, October 2004, pp. 710-717.
[29]Ayad Salhieh, Jennifer Weinmann, Manish Kochhal, and Loren Schwiebert, “Power Efficient Topologies for Wireless Sensor Networks,” the 30th International Conference on Parallel Processing, September 2001, pp. 156-163.
[30]Justin T. Kautz, Barry E. Mullins, Rusty O. Baldwin, and Scott R. Graham, “An Adaptable Energy-Efficient Medium Access Control Protocol for Wireless Sensor Network,” the 40th Hawaii International Conference on System Sciences, January 2007, pp. 292a.
[31]Deborah Estrin, Ramesh Govindan, John Heidemann, and Satish Kumar, “Next century challenges: Scalable Coordination in Sensor Networks,” the 5th annual ACM/IEEE international conference on Mobile Computing and Networking (MobiCom’99), August 1999, pp. 263-270.
[32]David Braginsky, and Deborah Estrin, “Rumor Routing Algorithm for Sensor Networks,” the 1st ACM international workshop on Wireless Sensor Networks and Applications, October 2002, pp. 22-31.
[33]Curt Schurgers, and Mani B. Srivastava, “Energy Efficient Routing in Wireless Sensor Networks,” the MILCOM on Communications for Network-Centric Operations: Creating the Information Force, Vol. 1, Oct 2001, pp. 357-361.
[34]Lakshminarayanan Subramanian, and Randy H. Katz, “An Architecture for Building Self-Configurable Systems,” IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing, August 2000, pp. 63-73.
[35]Wendi Rabiner Heinzelman, Amit Sinha, Alice Wang, and Anantha P. Chandrakasan, “Energy-Scalable Algorithms and Protocols for Wireless Sensor Networks,” the International Conference on Acoustics, Speech, and Signal Processing (ICASSP ‘00), Vol. 6, June 2000, pp. 3722-3725.
[36]Eugene Shih, Seong-Hwan Cho, Nathan Ickes, Rex Min, Amit Sinha, Alice Wang, and Anantha Chandrakasan, “Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom ‘01), July 2001, pp. 272-287.
[37]R. Ramanathan, and R. Rosales-Hain, “Topology control of multi-hop wireless networks using transmit power adjustment,” IEEE INFOCOM, March 2000, pp. 404-413.
[38]Sheetalkumar Doshi, Shweta Bhandare, and Timothy X. Brown, “An On-demand Minimum Energy Routing Protocol for a Wireless Ad Hoc Network,” ACM Mobile computing and Communications Review, Vol. 6, No. 3, July 2002, pp. 50-66.
[39]Stojmenovic, and X. Lin, “Power-aware Localized Routing in Wireless Networks,” IEEE Transaction on Parallel and Distributed Systems, Vol. 12, No. 11, Nov. 2001, pp. 1122-1133.
[40]Mao Ye, Chengfa Li, Guihai Chen, and Jie Wu, “EECS: An Energy Efficient clustering Scheme in Wireless Sensor Networks,” the 24th IEEE International Conference on Performance, Computing, and Communications, 7-9 April 2005, pp. 535-540.
[41]Guangyu Pei, and Charles Chien, “Low Power TDMA in Large Wireless Sensor Networks,” the Military Communications Conference, Vol. 1, October 2001, pp. 347-351.
[42]Sandeep S. Kulkarni, “TDMA Services for Sensor Networks,” the 24th International Conference on Distributed computing Systems Workshops, March 2004, pp. 604-609.
[43]Khaled A. Arisha, Moustafa A. Youssef, and Mohamed F. Younis, “Energy-aware TDMA-based MAC for sensor networks,” Computer Networks Journal, Vol. 43, No. 5, December 2003, pp. 539-694.
[44]Paul J.M. Havinga, and Gerard J.M. Smit, “Energy-efficient TDMA medium access control protocol scheduling,” the Asian International Mobile Computing Conference, November 2000, pp. 1-10.
[45]Amre El-Hoiydi, “Spatial TDMA and CSMA with Preamble Sampling for Low Power Ad Hoc Wireless Sensor Networks,” the IEEE symposium on Computers and Communications, July 2002, pp. 685-692.
[46]Michele Zorzi, “A New Contention-Based MAC Protocol for Geographic Forwarding in Ad Hoc and Sensor Networks,” the IEEE International Conference on Communications, Vol. 6, June 2004, pp. 3481-3485.
[47]Y. C. Tay, Kyle Jamieson, and Hari Balakrishnan, “Collision-Minimizing CSMA and its Applications to Wireless Sensor Networks,” IEEE Journal on Selected Areas in Communications, Vol. 22, No. 6, August 2004, pp. 1048-1057.
[48]Suresh Singh, and C.S. Raghavendra, “PAMAS: Power Aware Multi-Access protocol with Signaling for ad hoc networks,” ACM SIGCOMM Computer Communication Review, Vol. 28, No. 3, July 1998, pp. 5-26.
[49]Brian P. Crow, Indra Widjaja, Jeong Geun Kim, and Prescott T. Sakai, “IEEE 802.11 wireless local area networks,” IEEE Communications Magazine, Vol. 35, No. 9, September 1997, pp. 116-126.
[50]Masatoshi Sekine, Shinji Nakamura, and Kaoru Sezaki, “An Energy-Efficient Protocol for Active/Sleep Schedule Synchronization in Wireless Sensor Networks,” the IEEE Asia-Pacific Conference on Communications, August 2006, pp. 1-5.