臺灣博碩士論文加值系統

機率式路由的概念在過去數年間已經廣為盛行，其在無線網狀網路當中增進的資料傳輸效率也已經被普遍認同；然而到目前為止尚無任何研究著眼於將機率式路由在無線網狀網路上的效益，轉換為在無線感測網路上有效利用能源的優勢。在這篇論文當中，我們探討了在無線感測網路上設計機率式路由以發揮能源使用最大效益的可能性；我們專注設計一套無線感測網路上的路由協定，以追求負載平衡作為達成能源使用最大效益的目標。我們提出一項評估能源消耗的方程式作為我們能源使用效率的標準；特別的是，這套方程式其具備一些特殊的數學性質，藉由這些數學特性，有助於我們設計有效的路由協定，以達成能源使用最大效益的目標。經由模擬實驗可以證實我們所提出的機制能有效做到感測器之間的負載平衡，以延長全部無線感測網路的壽命。

Opportunistic routing has been widely approved because of its throughput improvement for wireless mesh networks; however, few researches focus on transforming its benefit into realizing energy efficiency for wireless sensor networks (WSNs). We notice that two common issues in fixed-path routing schemes, including single-path routing or multi-path routing, are that (1) a path may traverse through a fixed set of sensors, draining out their energy, and (2) packet retransmission over an unreliable link of any fixed-path may consume energy significantly. In this paper, we exploit two natural advantages of opportunistic routing, i.e., path diversity and the improvement of transmission reliability, to develop a distributed routing scheme (EFFORT) for prolonging the network-lifetime of a WSN. Unlike prior works on minimizing transmission delay in opportunistic routing, we propose a metric (called OEC) that assists each sensor in determining a suitable forwarding set for reducing the damage to the lifetime caused by each forwarding, and, thus, enable EFFORT to extend the network lifetime by implementing forwarder selection and relay prioritization based on OEC. Simulation results show that EFFORT achieves network-lifetime extension, as well as energy-cost minimization as compared with other routing protocols.

口試委員會審定書i
Acknowledgments iii
致謝v
中文摘要vii
Abstract ix
1 Introduction 1
2 Related Works 3
3 Opportunistic Routing for Lifetime Enhancement 5
3.1 The OEC metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 EFFORT Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Candidate Selection and Relay Prioritization . . . . . . . . . . . 12
3.2.2 Data Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 The Optimality of EFFORT . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Performance Evaluation 15
4.1 Compared protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.1 EFFORT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.2 OML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.3 GCF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.1 The lifetime of the network . . . . . . . . . . . . . . . . . . . . . 16
4.2.2 Minimum Residual Energy . . . . . . . . . . . . . . . . . . . . . 16
4.2.3 Number of Per-Hop Transmissions . . . . . . . . . . . . . . . . . 17
4.2.4 The energy consumption per bit . . . . . . . . . . . . . . . . . . 17
4.2.5 End-to-End Delay . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Lifetime-Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Path Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.5 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.6 Efficiency of Forwarder Selection . . . . . . . . . . . . . . . . . . . . . 20
5 Conclusions 23
6 appendix 25
6.1 Corollary associated with ^p . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Prioritization Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Monotonic Property and Candidate Extraction . . . . . . . . . . . . . . . 28
6.4 Candidate Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Bibliography 33

[1] A. Behzad and I. Rubin. Impact of power control on the performance of ad hoc
wireless networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE
Computer and Communications Societies. Proceedings IEEE, 2005.
[2] A. Behzad and I. Rubin. High transmission power increases the capacity of ad hoc
wireless networks. Wireless Communications, IEEE Transactions on, 5(1):156–165,
Jan. 2006.
[3] S. Biswas and R. Morris. Exor: opportunistic multi-hop routing for wireless networks.
In SIGCOMM ’05: Proceedings of the 2005 conference on Applications,
technologies, architectures, and protocols for computer communications, 2005.
[4] S. Chachulski, M. Jennings, S. Katti, and D. Katabi. Trading structure for randomness
in wireless opportunistic routing. In SIGCOMM ’07: Proceedings of the 2007
conference on Applications, technologies, architectures, and protocols for computer
communications, 2007.
[5] B. Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless
networks. In MobiCom ’00: Proceedings of the 6th annual international conference
on Mobile computing and networking, 2000.
[6] F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric ad-hoc routing:
of theory and practice. In PODC ’03: Proceedings of the twenty-second annual
symposium on Principles of distributed computing, 2003.
[7] R. Laufer, H. Dubois-Ferriere, and L. Kleinrock. Multirate anypath routing in wireless
mesh networks. In INFOCOM 2009. The 28th Conference on Computer Communications.
IEEE, 2009.
[8] MICAz Datasheet. http://www.xbow.com/.
[9] The Network Simulator NS-2. http://www.isi.edu/nsnam/ns/.
33
[10] J. Park and S. Sahni. An online heuristic for maximum lifetime routing in wireless
sensor networks. Computers, IEEE Transactions on, 55(8):1048–1056, 2006.
[11] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic
routing without location information. In MobiCom ’03: Proceedings of the 9th
annual international conference on Mobile computing and networking, 2003.
[12] C. Reis, R. Mahajan, M. Rodrig, D.Wetherall, and J. Zahorjan. Measurement-based
models of delivery and interference in static wireless networks. In SIGCOMM ’06:
Proceedings of the 2006 conference on Applications, technologies, architectures,
and protocols for computer communications, 2006.
[13] M.-J. Tsai, H.-Y. Yang, andW.-Q. Huang. Axis-based virtual coordinate assignment
protocol and delivery-guaranteed routing protocol in wireless sensor networks. In
INFOCOM 2007. 26th IEEE International Conference on Computer Communications.
IEEE, 2007.
[14] C. Wu, R. Yuan, and H. Zhou. A novel load balanced and lifetime maximization
routing protocol in wireless sensor networks. In Vehicular Technology Conference,
2008. VTC Spring 2008. IEEE, 2008.
[15] K. Zeng, W. Lou, J. Yang, and D. Brown. On geographic collaborative forwarding
in wireless ad hoc and sensor networks. In Wireless Algorithms, Systems and
Applications, 2007. WASA 2007. International Conference on, 2007.
[16] K. Zeng,W. Lou, and H. Zhai. On end-to-end throughput of opportunistic routing in
multirate and multihop wireless networks. In INFOCOM 2008. The 27th Conference
on Computer Communications. IEEE, 2008.
[17] K. Zeng, W. Lou, and Y. Zhang. Multi-rate geographic opportunistic routing in
wireless ad hoc networks. In Military Communications Conference, 2007. MILCOM
2007. IEEE, 2007.
[18] Z. Zhao, X. Zhang, P. Sun, and P. Liu. A transmission power control mac protocol
for wireless sensor networks. In Networking, 2007. ICN ’010. Sixth International
Conference on, 2007.