無線感測網路是由 Sink node與許多Sensor nodes所組成。Sensor nodes將其所感測的資料透過multi-hop方式回傳給Sink node。在資料回傳的過程中，越接近Sink node的Sensor nodes將因代傳較多的資料而使電量較快耗盡，整個WSNs因電量耗費不均而造成網路分割。本論文擬提出一有效的網路佈建、拓樸建構及排程協定，以達到延長感測網路的生命週期、降低資料傳送delay time、平衡各個Sensor nodes電量的消耗以及避免資料傳送時發生碰撞等目的。首先，我們以Mesh-base Topology為討論範圍，將Sensor Nodes建立一Balance 的虛擬樹狀結構。之後，我們分別研發了distance-based 及density-based 的擺放技術，使各Sensor Node能達到耗電平衡的目的。當各Sensor Nodes的擺放位置確定後，本論文再針對各Sensor Node進行MAC Scheduling，使其傳送資料時能避免衝撞，並且在最短時間內回傳給Sink Node。最後，我們將上述技術延伸其應用範圍至Random Deployed 的WSNs，由於在此環境下Sensor Node的擺設位置及密度均不規則，我們整合distance-based及density-based兩種技術，使原先在Mesh-based  WSNs 所開發的技術能應用在Random Deployed WSNs，並使各Sensor Node的耗電平衡以達到延長網路生命期之目的。實驗顯示，本論文所研發的協定能使各Sensor Node的耗電平衡以達到延長網路生命期之目的。

Wireless sensor networks (WSNs) comprise a sink node and a large number of sensor nodes. In the application of environmental monitoring, sensor nodes that are deployed far away from the sink node transmit the gathered information to the sink node in a multi-hop manner. Therefore, sensor nodes nearby the sink node tend to exhaust their energy earlier than other nodes due to their heavy traffic for packet forwarding. The unbalanced power consumption among sensor nodes may cause network partitioned. This paper proposes efficient node placement, topology control, and MAC scheduling protocols to prolong the sensor network lifetime, reduce the packet transmission delay, and avoid collision. Firstly, a virtual tree topology is constructed based on mesh-based WSNs. Then two node-placement techniques, namely distance-based and density-based deployments are proposed to balance the power consumption of sensor nodes. Finally, a collision-free MAC scheduling protocol is proposed to prevent the packet transmissions from collision. In addition, extension of the proposed protocols are made from the mesh-based WSN to the random deployed WSN, making the mechanisms developed for Mesh-based WSNs can be applied to random deployed WSNs. Simulation results reveal that the developed protocols can efficiently balance each sensor node’s power consumption and prolong the network lifetime in both mesh-based and random deployed WSNs.

圖目錄………………………………………………………………..…..ii
表目錄…………………………………………………………….……..v
第一章、 緒論……………………………………………..……………1
第二章、 網路環境與基本概念…………………………………………5
第三章、 電量平衡技術……..…………………………………...........13
A、 Topology Construction Phase………………………...…..13
B、 Node Placement Phase………………………………….…19
C、 MAC Scheduling Phase……………………….…….……31
第四章、 應用於隨機佈建之無線感測網路.…………….…………...40
第五章、 效能評估……………………………….……………....……45
第六章、 結論…………………….……………………………….…...55
參考文獻………………………………………………………….…….56
英文論文………………………………………………………………A1


圖目錄
圖(一)、網路拓撲架構圖。…………………………………………… .5
圖(二)、Sensor Nodes A and C因代傳較多資料而耗盡電量死亡。....6
圖(三)、為L型建樹，左右子樹之節點個數一樣。……………….…7
圖(四)、(a)一個3*3的Mesh 網路拓樸，Sensor Node上的數字代表代傳封包的次數。(b) Distance-based Scheme。(c)Density-based Scheme。……………………………………………………….9
圖(五)、vi表示Sensor Nodes的ID。Rslot表示Sensor Node會在指定的slot接收資料。Tslot表示Sensor Node會在指定的slot傳送資料。…………………………………….………………..10
圖(六)、延伸Mesh-based WSN所發展的技術至隨機佈點之WSN, 使其具Power Balance 之特性。……….…………………...…12
圖(七)、Topology Construction Phase。(a)為L-based建樹法示意圖。(b)一 的Mesh Topology，利用L-based建樹法建立之樹狀結構。……………………………………………………...14
圖(八)、Topology Construction演算法……………………………….15
圖(九)、(a)上邊界的Sensor Nodes其資料代傳量示意圖。(b)右邊界的Sensor Nodes其資料代傳量示意圖。……………………....22
圖(十)、(a)對角線上Sensor Nodes代傳示意圖。(b)leaf node之資料代傳量為1。……………………………………………………24
圖(十一)、(a)對角線上方Sensor Nodes之資料代傳量。(b)對角線下方Sensor Nodes之資料代傳量。……………………………....25
圖(十二)、在Distance-based Scheme中為滿足full coverage之感測距離示意圖。…………………………………………………..27
圖(十三)、Distance-based Scheme 依照資料代傳量調整與父節點之距離遠近。…………………………..………………………..28
圖(十四)、在Density-based Scheme中為滿足full coverage之Grid大小示意圖。…………………………………………………29
圖(十五)、Density-based Scheme依照資料代傳量控制Sensor Nodes佈點之密度。……………………………………………....31
圖(十六)、Calculate_Physical_Coordinate 演算法………………....32
圖(十七)、實際座標計算………………………………………….…...33
圖(十八)、MAC Scheduling演算法……………………………….…..37
圖(十九)、MAC Scheduling在3*3 Mesh Topology下排程之例子。...39
圖(二十)、Extending to Random Deployed WSN 演算法…………….42
圖(二十一)、Power Balance Mechanism應用在隨機佈點的WSNs。…43
圖(二十二)、評估Distance-based Scheme在Average End-to-End Delay上的效能………….……………………….…………….48
圖(二十三)、評估Density-based Scheme在Average End-to-End Delay上的效能………………………………………………...48
圖(二十四)、評估Distance-based Scheme在Network Lifetime上的效能………………………………………………………...49
圖(二十五)、評估Density-based Scheme在Network Lifetime上的效能………………………………………………………...50
圖(二十六)、評估Distance-based Scheme在剩餘電量標準差上的效能………………………………………………………...51
圖(二十七)、評估Density-based Scheme在剩餘電量標準差上的效能………………………………………………………...52
圖(二十八)、評估Distance-based Scheme在Accuracy上的效能…..53
圖(二十九)、評估Density-based Scheme在Accuracy上的效能……54
 
表目錄
表格(一)、模擬環境之相關參數………………………………………46

[1]	G. J. Pottie, W. J. Kaiser, “Wireless Integrate Network Sensors,” in Communications of the ACM, Vol. 43, no.5, pp. 551 – 558, May 2002.
[2]	D. Estrin, L. Girod, G. Pottie, and M. Strivastava, “Instrumenting the World With Wireless Sensor Networks,” in International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2001.
[3]	D. Estrin, R. Govindan, “Next Century Challenges: Scalable Coordination in Sensor Networks,” in Mobicom 1999, August 1999, pp. 263 – 270.
[4]	C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, “Topology Management for Sensor Networks: Exploiting Latency and Density,” in Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking & Computing (MobiHoc), June 2002, pp. 135 - 145.
[5]	K. Sohrabi, J. Gao, V. Ailawadhi, G. Pottie, “Protocols for Self-organization of a Wireless Sensor Network,” in IEEE Personal Communications Magazine, October 2000, pp. 16 – 27.
[6]	Woo and D. Culler, “A Transmission Control Scheme for Media Access in Sensor Networks,” in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, July 2001, pp. 221 – 235.
[7]	B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” in Mobicom 2001, July 2001.
[8]	C. Barrett, A. Marathe, M. Marathe, and M. Drozda, “Characterizing the Interaction Between Routing and MAC Protocols in ad hoc Networks,” in Proceedings of the 3rd ACM International Symposium on Mobile ad hoc networking & computing (MobiHoc), June 2002, pp. 92 – 103.
[9]	J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, “Topology control for wireless Sensor networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, September 2003, pp. 286 - 299.
[10]	Y.-C. Tseng, Y.-N. Chang, and P.-H. Tseng, “Energy-efficient topology control for wireless ad hoc Sensor networks,” in Proceedings of International Computer Symposium (ICS), 2002.
[11]	S. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Radio Networks using Transmit Power Adjustment,” in Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom), March 2000, pp. 404 - 413.
[12]	W. Li and C. G. Cassandras, “A Minimum-Power Wireless Sensor Network Self-Deployment Scheme,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), March 2005, pp. 1897 - 1902.
[13]	P. Cheng, C. N. Chuah, and X. Liu, “Energy-aware Node Placement in Wireless Sensor Networks,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), November 2004, pp. 3210 - 3214.