臺灣博碩士論文加值系統

在無線感測網路的應用上，多半是為了針對某區域進行環境的監測與資料的
蒐集。感測節點受限於所搭載的通訊裝置範圍有限，感測節點之間必須透過通訊
裝置以互相交換資料的方式進行資料的蒐集。由於感測節點所搭載的能源經常是
不可補充的，並且使用通訊裝置將會損耗節點能源。能源的耗盡將會使節點停止
運作，對於能源的使用上必須非常謹慎，對於不必要的遞送路徑必須加以避免，
避免感測節點的能源浪費。
地理式路由是感測節點藉著搭載的全GPS接收器來取得節點自身座標，以節
點座標資訊來進行路由。地理式路由節省了傳統的結構化路由在建立全域網路拓
樸的動作，因為建立與維護這些網路拓樸會大量消耗感測節點所搭載的能源。地
理式路由策略上是選擇與目標最短距離的節點來進行轉遞，當網路中存在障礙物
或空洞時，依照最短路徑的選擇時，將有可能使得封包遞送路徑遇上障礙物，將
造成遞送路徑顯得複雜，同時當節點能源用盡時，封包的遞送上將因為節點能源
用盡而使得封包遺失，如此將造成封包遞送率下降。
考量上述觀點，在本篇論文中，對於障礙物或空洞等問題，我們提出了區塊
分佈演算法，這是一種使感測節點能夠以預覽視野方式來避免不必要的遞送路徑
之策略，同時考量感測節點的能源消耗狀態以轉遞平衡消耗演算法來決定轉遞節
點。透過區塊分佈演算法將可以避免感測節點多餘的封包遞送動作，同時加入了
能源耗損程度的考量，使得感測節點在封包轉遞的選擇上，能夠避免選擇到剩餘
能源低麋的感測節點。

Wireless sensor network applications such as environmental monitoring and data
gathering are meant to operate as long as possible. Since each wireless node has
limited communication range, packets are generally delivered hop by hop, at the
expense of power consumption, towards the intended destinations. However, when any
intermediate node on a path has depleted its power, i.e., a hole emerges, packet
delivery fails and subsequently another new route must be resolved, so as to restore
packet transfer. Therefore, a well-planned routing strategy that avoids ineffective
transmissions on account of holes is essential to overall network performance.
This thesis presents a load-aware geographic routing scheme that allows for three
determinants for each of qualified neighbor nodes on demand: residual energy, the
amount of dissipated power for current transmission, and its distance away from the
destination. Each neighbor node is thus associated with a score per packet; the node
which scores highest becomes the next hop to forward the packet. Such a selection is
done hop by hop until the packet reaches its destination. Our strategy is to prevent
packets from traversing a certain set of nodes repeatedly, causing severe power drain
on these nodes. Accordingly, workload is better distributed in our architecture so that
holes are less likely to shape. In addition, we propose an algorithm, namely the
Available Relay Block algorithm, that is performed a priori to identify which areas
towards the given destination contain dead-end nodes. These identified areas are ruled
out of consideration by our load-aware strategy. By doing so, our routing strategy is
kept operable, despite the presence of holes, such that network lifetime can be
maximized. Performance evaluation is conducted via QualNet. Simulation results
indicate the effectiveness of our design and outlines several directions to work toward
in the future.

中文摘要 .......................................................................................................................... i
英文摘要 .......................................................................................................................... ii
致謝 ............................................................................................................................... iii
目錄 ................................................................................................................................ iv
表目錄 .............................................................................................................................. v
圖目錄 ............................................................................................................................. vi
第一章 簡介 .............................................................................................................. 1
第二章 文獻探討 ...................................................................................................... 3
2.1 GPSR: Greedy Perimeter Stateless Routing for Wireless Networks ............ 3
2.2 GPSRWDR:Geographic Forwarding With Dead-End Reduction in Mobile
Ad Hoc Networks ......................................................................................... 5
2.3 EAGR: Energy Aware Greedy Routing scheme for wireless ad hoc
networks ....................................................................................................... 9
第三章 研究方法 .................................................................................................... 10
3.1 地理式路由封包遞送 ................................................................................ 10
3.2 Dead-End 避免機制 ................................................................................... 12
3.3 能源平均消耗策略 .................................................................................... 20
3.4 效益分析 .................................................................................................... 25
第四章 實驗 ............................................................................................................ 26
4.1 實驗平台 .................................................................................................... 26
4.2 實驗環境假設及參數 ................................................................................ 26
4.3 實驗方式 .................................................................................................... 27
4.4 策略封包格式 ............................................................................................ 27
4.5 實驗數據 .................................................................................................... 30
第五章 結論與未來研究方向 ................................................................................ 32
參考文獻 ........................................................................................................................ 33
作者簡歷 ........................................................................................................................ 35

B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing For
Wireless Networks,” Proc. 6th Annual Int''l Conf. on Mobile Computing and
Networking. Boston: ACM Press, pp.243-254, 2000.
[2] C.H.Chou, K.F.Ssu,and H.C. “Geographic Forwarding with Dead-End
Reduction in Mobile Ad Hoc Networks” IEEE Transactions on Vehicular
Technology, Vol 57, Issue: 4, July 2008.
[3] S. Sharma, H.M. Gupta, and S. Dharmaraja, “EAGR: Energy Aware Greedy
Routing Scheme For Wireless Ad Hoc Networks” Performance Evaluation of
Computer and Telecommunication Systems, 2008, pp. 122 - 129, June 2008.
[4] R. Jurdak, P. Baldi, Senior, and C. V. Lopes, “Adaptive Low Power Listening
for Wireless Sensor Networks, ” IEEE Transactions On Mobile Computing,
Vol. 6, No 8 pp.988-1004, Aug 2007.
[5] G. Wang, G. Cao, P. Berman, and T. F. La Porta, “Bidding Protocols For
Deploying Mobile Sensors,” IEEE Transactions on Mobile Computing, Vol. 6,
No. 5, pp. 563-576, May 2007.
[6] Y.C. Wang, C.C. Hu, and Y.C. Tseng, “Efficient Placement and Dispatch of
Sensors in a Wireless Sensor Network,” IEEE Transactions on Mobile
Computing, Vol. 7, No. 2, pp.262-274, Feb 2008.
[7] F. Yu, Y. Choi, S. Park, E. Lee, Ye Tian, and Sang-Ha Kim, “Virtual Circle
Based Geometric Modeling of Holes for Geographic Routing,” IEEE Wireless
Communications and Networking Conference, pp.2426-2430, 2008.
[8] Z. Zhang, M. Ma, and Y. Yang, “Energy-Efficient Multihop Polling in
Clusters of Two-Layered Heterogeneous Sensor Networks,” IEEE
Transactions on Computers, Vol. 57, NO. 2, pp.231-245, Feb 2008.
[9] IEEE, “IEEE Std 802.15.4, 2006” Institute of Electrical and Electronics
Engineers, Inc., 8 Sept 2006.
[10] 劉恆碩，在無線感測網路中使用以時間導向為主的資料散播，國立雲林科技大學電機工程研究所，2008。
[11] 許酉遠，基於無線感測網路不規則訊號之凸包協助定位方法，國立雲林科技大學電機工程研究所，2009。
[12] 謝嘉維，無線感測網路之動態資料綁定機制的設計與實作，國立雲林科技大學電機工程研究所，2009。
[13] Scalable-networks Forums http://www.scalable-networks.com/boards/.
[14] Embedded Networks Laboratory http://enl.usc.edu/.
[15] 皮托科技股份有限公司 http://www.pitotech.com.tw/。
[16] 柯老师的Qualnet索引http://140.116.72.80/~smallko/qualnet/qualnet.htm。
[17] MPR-MIB Users Manual
http://www-db.ics.uci.edu/pages/research/quasar/MPR-MIB%20Series%20Us
er%20Manual%207430-0021-06_A.pdf.
[18] 曾煜棋、潘孟鉉、林致宇，無線區域及個人網路，知城出版社。
[19] 柯志亨、陳瑞馨、鄧德雋、程榮祥、林舜英，計算機網路實驗－使用QualNet
模擬工具實作，鼎茂出版社。