無線路由演算法 (wireless routing algorithm) 一直是個重要的議題，過去在這方面的研究相當多，然而可以實際運行的卻寥寥無幾。過去所提出的方法有的需更改規格、有的會有副作用產生，甚至有的方法是建立於理想性的假設；因此，設計一個有效率且可以與既有的無線網路技術共存、合作的方法仍有待解決，而本篇論文是分析IEEE 802.15.4 ZigBee 路由演算法 [2] 的行為，進而提出改進的方法。 ZigBee 路由演算法在建立路徑 (route discovery) 的過程中會送出許多的route request (RREQ) command 及route reply (RREP) command；經由實際模擬與觀察，我們發現ZigBee 路由演算法會產生大量的RREQ 及RREP commands，如預期一般，此結果使得ZigBee 設備消耗更多的電力，另外也間接地影響整個網路的傳輸效能 (throughput)。傳送的封包數目越多顯示通道 (channel) 競爭的情形會越激烈， 由於Carrier-Sense-Multiple-Access with Collision-Avoidance (CSMA-CA) algorithm 的特性，一旦發生channel busy，網路設備就必須額外等待一段時間才能再次嘗試送出封包，因而造成ZigBee 設備高耗電量與低傳輸效能。 ZigBee 路由演算法使用延遲傳送RREQ 封包時間來減少RREQ 封包產生的數量。此方法為每一網路節點收到RREQ 封包後會暫時等待一段時間 (稱為RREQ jitter)，經由比較這段時間所有收到的RREQ 封包的forward cost，只送出一個forward cost 最佳之RREQ 封包。ZigBee 路由演算法欲藉由調整RREQ jitter來減少RREQ 與RREP commands 的數量，這對網路的穩定性有很大的幫助，然而規格書裡並沒有明確說明RREQ jitter 須如何設定。我們從觀察模擬結果中分析RREQ jitter 參數的影響，模擬結果顯示使用RREQ jitter 會造成建立一條路徑需耗費更長時間，換言之，ZigBee 設備傳送資料的起始時間被延後。也因此，此論文將提出一個相容於既有的ZigBee 路由演算法且能兼顧RREQ 封包數量與路徑建立的時間的方法，此方法稱為Listen-Before-Transmit (LBT) 演算法。 即使ZigBee 路由演算法使用RREQ jitter，它在執行route discovery 時所產生的控制封包依然很多，針對此問題，我們更進一步分析出四種條件可以使節點有效的減少控制封包的數量，並且可以加快建立路徑的時間；更重要的是，所得到的優點完全不須修改ZigBee 路由演算法。最後，我們亦針對ZigBee 路由演算法分析所觀察到的現象。 本篇論文分成六章，第一章針對ZigBee 路由演算法做簡單的介紹，第二章介紹我們所提出的LBT 演算法，第三章說明如何減少ZigBee 執行route discovery時所產生的控制封包方法和ZigBee 路由演算法的特性，第四章是模擬和分析的部份，第五章是比較現有的相關技術和ZigBee 之間的差異，第六章是做總結。 Wireless routing algorithm is an important issue in last decade. Many research results about such topic have been proposed. However, most of proposed routing protocols are not able to actually work well. This is because that these approaches need to revise standard specifications and/or make some ideal assumptions. It’s important to find out an efficient routing protocol that is compatible with the contemporary wireless network technologies. The main goal of this thesis is to analyze the behavior of IEEE 802.15.4 ZigBee routing algorithm [2] and then find out all the improvable parts in standard. ZigBee routing algorithm may generate a lot of route request (RREQ) commands and route reply (RREP) commands when network starts the route discovery procedure. From our simulation results, we found that ZigBee routing algorithm really generates a lot of RREQ and RREP commands and it will make ZigBee devices consume more power sources and it will downgrade the network throughput. The reason is that as more packets are transmitted, more contentions will be resulted. Based on the carrier sense multiple access with collision avoidance (CSMA-CA) algorithm, if the channel becomes busy, ZigBee devices need take a longer time for sending packets successfully. Consequently, ZigBee devices will consume much more power and obtain lower throughput. ZigBee routing algorithm adopts the RREQ jitter to reduce the amount of RREQ and RREP commands. It is very helpful to reduce the network overhead. Unfortunately, ZigBee specification doesn’t specifically indicate how to set the RREQ jitter. In this dissertation, we observe the relationship between system performance and the RREQ jitter parameter via simulations. From observation, we found that there is a disadvantage of using the RREQ jitter. A larger of RREQ jitter is applied, a longer time of route establishment will be. In other words, ZigBee device takes a long time before data transmissions. In order to resolve this problem, we will propose the listen-before-transmit (LBT) algorithm, which is compatible with ZigBee routing algorithm and it is very easy to be implemented. There is still a lot of command frames during the route discovery procedure, even if ZigBee routing algorithm uses the RREQ jitter. We analyze the protocol behavior and conclude that there are four cases the device can stop sending the useless command frames. By stopping sending useless command frames, the latency of routes establishment is shortened. The most important thing is that using such case detection strategy is fully compatible with standard ZigBee routing algorithm. In addition, we will highlight the observed features of ZigBee routing algorithm in this dissertation. There are six chapters in this dissertation. Chapter 1 will introduce the ZigBee routing algorithm. Chapter 2 illustrates the procedure of the listen-before-transmit (LBT) algorithm. Chapter 3 discusses the ways that can reduce the command frames during the route discovery procedure and the unique features of ZigBee routing algorithm. Chapter 4 shows the simulation results. Chapter 5 compares the ZigBee with the other related wireless technologies. Chapter 6 concludes this dissertation.
