臺灣博碩士論文加值系統

無線感測器網路路由協定研究方面，不規則傳輸造成的干擾影響是一個重要
的研究課題。因此本論文提出一使用不規則傳輸模型之能量效率階層分群路由演
算法設計(energy efficient hierarchical clustering routing algorithm, EHCA)，利用模
糊分群演算法進行分群再分群的動作以平衡每一族群間的能量消耗。在挑選超群
首節點、網格群首節點與群首節點方面考量能量最高者為之，同時根據DOI 模
組模擬不規則傳輸的狀況，在轉傳節點挑選機制上讓干擾狀況較為嚴重的節點不
會形成轉傳節點。接著再以最短路徑演算法找出最佳權重參數值，來規劃每個節
點的最佳轉傳路徑。最佳權重參數值是以各節點的剩餘電量、干擾與傳輸距離為
考量依據，來計算節點間的最佳傳輸路徑。主要的目的是為了在任何隨機分布的
網路中平衡每一次網路拓樸中的每顆節點平均能量消耗，進而延長整體網路節點
存活時間，使網路能有更佳的能源使用效率。
模擬結果顯示，EHCA協定在每封包的平均能量損耗上較MMERM、LEACHM
與LEACHCM 協定至少節省約25%以上。此外，網路第一顆節點的電量耗盡時間
仍較三者協定延長至少48%的時間。由此可知EHCA 協定能夠有效的延長網路
所有節點的存活時間，並提高能量的使用效率。

In the research of routing protocols for wireless sensor networks, the interference
caused by the degree of irregularity is an important issue in the routing protocol study.
Thus, this work proposes an energy efficient hierarchical clustering routing algorithm
with degree of irregularity for wireless sensor networks (EHCA) to deal with this
problem.
This routing algorithm uses a fuzzy C-Means (FCM) algorithm successively
twice to divide the network nodes into clusters to balance the energy consumption for
each cluster. We select the node with the highest residual energy as super cluster head,
grid cluster head and cluster head. According to the degree of irregularity model
which emulates the irregular transmission situation, the relay node selection
mechanism ensures that the significantly interfered nodes will not to become the relay
nodes. Then, a shortest path algorithm is used to conduct the optimal weighting
parameters for finding the best relaying route for each node. The optimal weighting
parameters functions of remaining energy, interference, and transmission distance of
each node. The main objective of the proposed method is to balance the energy
consumptions for network nodes, and hence prolong the survival time of nodes in
arbitrarily randomly distributed sensor networks and increase the energy consumption
efficiency.
According to the simulation results, the proposed routing protocol, named EHCA,
iii
reduces 25% of the average energy consumption as compared with the routing
protocols, MMERM, LEACHM, and LEACHCM. In addition, the electrical survival
time of the first node to be exhausted extends at least 48% than that of the other three
routing protocols. Thus, EHCA not only efficiently extends the survival time of all
nodes in the network but also increases the energy utilization.

中文摘要 ................................................................................................................. I
英文摘要 ................................................................................................................ II
目 錄 ...................................................................................................................... V
表目錄 ................................................................................................................. VII
圖目錄 ................................................................................................................ VIII
第一章 緒論 .......................................................................................................... 1
1.1 研究背景 ................................................................................................. 1
1.2 研究動機及目的 ..................................................................................... 3
1.3 文獻探討 ................................................................................................. 3
1.4 論文架構 ............................................................................................... 16
第二章 無線感測器網路與相關技術簡介 .......................................................... 17
2.1 前言 ....................................................................................................... 17
2.2 無線感測網路簡介 ................................................................................ 17
2.3 不規則傳輸模型 ................................................................................... 20
2.4 模糊C-平均值分群演算法 ................................................................... 24
2.5 路徑選擇演算法 ................................................................................... 26
2.6 結語 ....................................................................................................... 29
第三章 能量效率之階層分群路由設計 .............................................................. 30
3.1 前言 ....................................................................................................... 30
3.2 EHCA 協定之設計 ................................................................................ 30
3.2.1 網路初始化................................................................................. 32
3.2.2 族群劃分階段 ............................................................................. 33
3.2.3 路徑選擇階段 ............................................................................. 35
3.2.4 資料收集階段 ............................................................................. 39
3.3 結語 ...................................................................................................... 40
第四章 EHCA 路由演算法效能之模擬與分析................................................... 42
vi
4.1 前言 ...................................................................................................... 42
4.2 模擬環境設定 ....................................................................................... 42
4.3 模擬驗證與分析 ................................................................................... 44
4.4 結語 ...................................................................................................... 59
第五章 結論與未來研究方向 ............................................................................. 60
5.1 結論 ....................................................................................................... 60
5.2 未來方向 ............................................................................................... 60
參考文獻 .............................................................................................................. 62

[1] J. M. Kahn, R. H. Katz and K. S. J. Pister, “Next century challenges: mobile
networking for smart dust,” Proceedings of the International Conference on
Mobile Computing and Networking, 1999, pp. 271-278.
[2] Y. T. Hoi, F. T. Kim and L. L. Ka, “ZigBee sensor network for advanced
metering infrastructure,” Proceedings of the International Conference on
Consumer Electronics, Jan. 2010, pp. 95-96.
[3] G. W. Allen, K. Lorincz, M. Ruiz, O. Marcillo, J. Johnson, J. Lees and M. Welsh,
“Deploying a wireless sensor network on an active volcano,” IEEE Internet
Computing, vol. 10, no. 2, Mar. 2006, pp. 18-25.
[4] 林冠璋，使用無線感測器網路之自動化害蟲生態監測系統研製，碩士論文，
台北科技大學機電整合研究所，台北，2007。
[5] C. Sukwon, K. Nakyoung, C. Hojung and H. Rhan, “Microsensor node for air
pollutant monitoring：hardware and software issues,” Sensors, vol. 9, issue 10,
2009, pp. 7970-7987.
[6] 劉奕崴，應用於健康照顧之無線感測器網路監測系統開發，碩士論文，台灣
大學生物產業機電工程學系，台北，2010。
[7] J. Shin and C. Suh, “CREEC: chain routing with even energy consumption,”
Journal of Communications and Networks, issue 1, Feb. 2011, pp. 17-25.
[8] G. M. Shafiullah, A. Azad and A. B. M. S. Ali, “Energy-efficient wireless MAC
protocols for railway monitoring application,” IEEE Transactions on Intelligent
Transportation Systems, vol. 14, issue 2, June 2013, pp. 649-659.
[9] Z. Guo, Y. Guo, F. Hong, Z. Jin, Y. He, Y. Feng and Y. Liu, “Perpendicular
intersection: locating wireless sensors with mobile beacon,” IEEE Transactions
on Vehicular Technology, vol. 59, no. 7, Sep. 2010, pp. 3501-3509.
[10] W. Li and W. Zhang, “Coverage analysis and active scheme of wireless sensor
networks,” Wireless Sensor Systems, vol. 2, issue 2, June 2012, pp. 86-91.
[11] S. H. Jokhio, I. A. Jokhio and A. H. Kemp, “Node capture attack detection and
defence in wireless sensor networks,” Wireless Sensor Systems, vol. 2, issue 3,
Sep. 2012, pp. 161-169.
[12] 王信智，無線感測網路室內定位分析與應用，碩士論文，台北科技大學自動
化研究所，台北，2010。
63
[13] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient
communication protocol for wireless microsensor networks,” Proceedings of the
IEEE Conference on System Sciences, Jan. 2000, pp. 1-10.
[14] K. Akkaya and M. Younis, “A survey on routing protocols for wireless sensor
networks,” Ad Hoc Networks, vol. 3, issue 3, May 2005, pp. 325-349.
[15] H. Takagi and L. Kleinrock, “Optimal transmission range for randomly
distributed packet radio terminals,” IEEE Transactions on Communication, vol.
32, issue 3, 1984, pp. 246-257.
[16] Y. Xu, J. Heidemann and D. Estrin, “Geography-informed energy conservation
for ad-hoc routing,” Proceedings of the ACM/IEEE International Conference on
Mobile Computing and Networking, 2001, pp. 70-84.
[17] Y. Yu, D. Estrin and R. Govindan, “Geographical and energy-aware routing: a
recursive data dissemination protocol for wireless sensor networks,” UCLA
Computer Science Department Technical Report, 2001.
[18] W. Heinzelman,z J. Kulik and H. Balakrishnan, “Adaptive protocols for
information dissemination in wireless sensor networks,” Proceedings of the
ACM/IEEE International Conference on Mobile Computing and Networking,
Aug. 1999, pp. 174-85.
[19] C. Intanagonwiwat, R. Govindan and D. Estrin, “Directed diffusion: a scalable
and robust communication paradigm for sensor networks,” Proceedings of the
ACM/IEEE International Conference on Mobile Computing and Networking,
2000, pp. 56-67.
[20] D. Estrin, R. Govindan, J. Heidemann and S. Kumar, “Next century challenges:
scalable coordination in sensor networks,” Proceedings of the ACM/IEEE
International Conference on Mobile Computing and Networking, Aug. 1999, pp.
263-270.
[21] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient
communication protocol for wireless microsensor networks,” Proceedings of the
IEEE Conference on System Sciences, Jan. 2000, pp. 1-10.
[22] Y. R. Tsai, “Coverage-preserving routing protocols for randomly distributed
wireless sensor networks,” IEEE Transactions on Wireless Communications, vol.
6, no. 4, 2007, pp. 1240-1245.
[23] S. Lindsey and C. S. Raghavendra, “PEGASIS: Power-efficient gathering in
sensor information systems,” Proceedings of IEEE Conference on Aerospace, vol.
64
3, 2002, pp. 1125-1130.
[24] J. H. Chang and L. Tassiulas, “Maximum lifetime routing in wireless sensor
networks,” ACM/IEEE Transactions on Networking, vol. 12, issue 4, 2004, pp.
609-619.
[25] C. Rahul and J. Rabaey, “Energy aware routing for low energy ad hoc sensor
networks,” Proceedings of the IEEE Conference on Wireless Communications
and Networking, vol. 1, Mar. 2002, pp. 350-355.
[26] S. Dulman, T. Nieberg, J. Wu and P. Havinga, “Trade-off between traffic
overhead and reliability in multipath routing for wireless sensor networks,”
Proceedings of the IEEE Conference on Wireless Communications and
Networking, vol. 3, Mar. 2003, pp. 1918-1922.
[27] K. Sohrabi and J. Pottie, “Protocols for self-organization of a wireless sensor
network,” IEEE Personal Communications, vol. 7, issue 5, 2000, pp. 16-27.
[28] T. He, J. A. Stankovic, C. Lu and T. Abdelzaher, “SPEED: a stateless protocol for
real-time communication in sensor networks,” IEEE Conference on Distributed
Computing Systems, 2003, pp. 46-55.
[29] 劉立群，無線感測網路中建立有效平衡資料負載的低延遲資料收集樹，碩士
論文，中華大學資訊工程學系，台北，2003。
[30] S. Lindsey, C. Raghavendra and K. M. Sivalingam, “Data gathering algorithms
in sensor networks using energy metrics,” IEEE Transactions on Parallel and
Distributed Systems, vol. 13, no. 9, Sep. 2002, pp. 924-935.
[31] S. Chatterijea and P.Havinga, “A dynamic data aggregation scheme for wireless
sensor networks,” Proceedings of the Program for Research on Integrated
Systems and Circuits, Nov. 2003, pp. 26-27.
[32] 司仕豪，適用於隨機分佈無線感測器網路之多指標節能路由協定，碩士論
文，台北科技大學電機工程系碩士班，台北，2009。
[33] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A survey on
sensor networks,” IEEE Communications Magazine, 2002, pp. 102-114.
[34] W. B. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “An
application-specific protocol architecture for wireless microsensor networks,”
IEEE Transactions on Wireless Communication, vol. 1, Oct. 2002, pp. 660-670.
[35] G. Zhou, T. He, S. Krishnamurthy and J. Stankovic, “Models and solutions for
radio irregularity in wireless sensor networks,” ACM Transactions on Sensor
65
Networks, vol. 2, issue. 2, May 2006, pp. 221-262.
[36] 林政翰，適用於無線感測網路的多功率傳送跳數定位演算法，碩士論文，台
北科技大學電機工程系碩士班，台北，2012。
[37] J. C. Bezdek, Fuzzy Mathematics in Pattern Classification, Ph.D. dissertation,
Applied Math. Center, Cornell University, Ithaca, 1973.
[38] W. Feng, L. Zhang and J. M. H. Elmirghani, “Energy saving geographic routing
in ad hoc wireless networks,” Proceedings of the IET Communications, vol. 6,
issue 1, Jan. 2012, pp. 116-124.
[39] J. S. Lee, Y. M. Wang and C. C.Shen, “Performance evaluation of ZigBee-based
sensor networks using empirical measurements,” IEEE International Conference
on Cyber Technology in Automation, May 2012, pp. 27-31.