本論文的主要目的在於探討不同的無線網路(例如：無線感測網路(Wireless Sensor Networks，簡稱WSNs)、與無線網格網路(Wireless Mesh Networks，簡稱WMNs))中，基於不同的傳輸效益訴求(例如：降低通訊成本(communication cost)以達到節能目的、降低端與端傳輸延遲成本(end-to-end delay cost)增加網路傳輸吞吐量(throughput))而所運用之具成本效益路由機制(cost-effective routing schemes)之相關設計議題。

近年來，無線感測網路已廣泛地導入戰場監控、災害通報等廣大範圍之偵測應用中。這些應用所建立之無線傳輸方式乃基於眾多無線感測節點回傳資料至散布四周之收集節點(Sinks)，稱作多對多傳輸(Many-to-many communication)。由於多播傳輸(Multicast)方式允許網路中的節點僅執行一次傳送，將感測資料傳送給多個目的節點，以能夠節省網路頻寬及電源消耗。因此，本論文首先針對多對多傳輸應用系統設計一套節能多播傳輸協定，使得網路中之無線感測節點能藉由計算多種通往所有目的收集點之潛在的多播傳輸樹(Multicast trees)路由路徑之多播傳輸成本，評估出具有最低成本之多播傳輸樹。實驗結果證實所提出之多播傳輸路由演算法可有效降低整體網路通訊成本消耗，提高傳輸效能，進而提升網路生命週期。

有鑑於油汙或是生化汙染源外洩於海中不僅對近海環境具有潛在的威脅與傷害甚至危及周邊區域的經濟發展。為了能即時地、持續地、與節能地蒐集水汙染擴及範圍資訊，本論文進而提出一套運用水上無線感測網路(Waterborne Wireless Sensor Network，簡稱WWSN)技術之水汙染偵測與監控機制，定名為AquaView，以追蹤水面汙染源不斷擴散與移動的範圍藉以提升清除行動之效率。在評估AquaView機制中感測節點追蹤汙染源擴散範圍效能方面，本論文根據導致物件在海面漂流運動的三個主要因素，即海流、海風、以及海浪之運動特性，提出三維物件漂浮運動模型(3D Floating Mobility Model，簡稱3D FMM)模擬感測節點運動軌跡。此運動模型經數值模擬驗證，確實能精準重現感測節點漂浮在海面上的三維運動軌跡。而AquaView機制僅需極低的通訊成本，便能即時蒐集到準確的汙染源擴散範圍資訊，達到令人滿意的監控效果。

任意路徑路由(Anypath routing)的傳輸概念乃是運用無線傳播媒介(wireless medium)蘊含的廣播與空間多樣性(spatial diversity)之特性，以強化無線網格網路之封包傳遞可靠度進而提升網路效能。過去此類研究乃是基於網路中無線線路(wireless links)之封包傳輸率(packet delivery ratios)，聚焦在找尋每個節點適合之轉送集合(forwarding set)，此集合由數個鄰點組成，以提升封包傳送可靠度進而降低至目的節點之傳輸成本。然而這些方法忽略節點間為了傳遞封包而相互競爭傳輸通道所衍生之封包預期傳送時間(Expected Packet Transmission Time，簡稱EPTXT)成本，以至於網路傳輸吞吐效能(throughput performance)可能因而降低。對此，本論文對此設計一套基於封包預期傳送時間結合G/D/1排隊理論之數學分析模型，預測節點透過轉送集合往目的節點傳送封包之端與端傳輸延遲(end-to-end delay)時間。接著以封包預期傳送時間與無線線路之封包傳輸率作考量，進一步提出跨階層任意路徑路由(Cross-layer Anypath Routing，簡稱CAR)機制以為每個節點篩選出最適合之傳送集合。所提出之數學分析模型經數值模擬之驗證，確實能在低流量之情境準確預測節點所傳輸的封包經由給定之任意路徑至目的節點之端與端傳輸延遲時間之期望值。再者所提出之跨階層任意路徑路由機制更能較以往的方法讓每個節點具有較低的端與端傳輸延遲時間以至於整體網路傳輸吞吐效能有所提升。

This dissertation is aimed at addressing critical issues of designing cost-effective routing protocols in order to enhance different performances (i.e., decreasing communication cost for improving energy-saving performance, reducing end-to-end delay cost for increasing throughput performance) over various wireless networks (i.e., Wireless Sensor Networks (WSNs), and Wireless Mesh Networks (WMNs)).

WSNs make possible many new applications in a wide range of application domains. Many of these applications are based on a many-to-many communication paradigm in which multiple sensor nodes send their sensed data to multiple sinks. To support these many-to-many applications, this dissertation proposes an energy-efficient transport protocol in which each source sensor evaluates the multicast costs of various potential multicast trees between it and the destination sinks and then selects the tree with the minimum communication overhead. The simulation results demonstrate that the proposed multicast routing algorithm yields a significant reduction in the total energy consumption, and therefore enables a notable improvement in the network lifetime.

Spillages of pollutants such as oil or biochemical materials at sea have the potential to damage not only the offshore environments, but also the regional economy. In order to monitor spilled pollutions in the real-time, continuous, and energy-efficient fashions, this dissertation develops an aquatic-pollution detection and tracking scheme, designated as AquaView, based on a WSN deployed over an offshore region (i.e., a Waterborne Wireless Sensor Network (WWSN)) to track the moving boundary of a pollution spill such that cleanup operation can be effectively monitored and controlled. In evaluating the boundary tracking performance of AcquaView, a 3D Floating Mobility Model (3D FMM) is used to simulate the movement of the sensor nodes floating on the ocean surface. The numerical results confirm that the 3D FMM model accurately reproduces the statistical features of the ocean current, wind and surface wave effects on the 3D trajectories of the sensor nodes. Moreover, it is shown that AquaView achieves a significantly improvement in a satisfactory boundary estimation performance and a low communication cost.

Anypath routing has been proposed as a means of enhancing the performance of WMNs by exploiting the inherent broadcasting and spatial diversity properties of a wireless medium. Previous studies have focused on the problem of identifying an appropriate forwarding set at each node based on the packet delivery ratios of the wireless links within the network. However, the schemes proposed in these studies may result in a significant degradation of the throughput performance since they ignore the potential Expected Packet Transmission Time (EPTXT) overhead incurred by the nodes in contending for the shared channel resources in order to transmit a packet to its forwarding set. Accordingly, this dissertation proposes an analytical model for estimating the end-to-end delay of a node in delivering a packet to a given destination via its forwarding set based on the EPTXT of the node and G/D/1 queueing theory. A Cross-layer Anypath Routing (CAR) scheme is then proposed for determining the most suitable forwarding set at each node based on an Expected Time of Anypath Transmissions (ETATX) metric, as determined by the EPTXT of each node along the anypath and the packet delivery ratios of the corresponding links. The numerical results confirm that the proposed analytical model provides an accurate estimation of the end-to-end delay performance of a node in transmitting a packet along an anypath to the destination in light load regime. Moreover, it is shown that compared with existing anypath routing schemes, CAR results in a lower end-to-end packet forwarding delay, and therefore increases the throughput at each node.

[1] W. R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor Networks,” in Proc. of ACM MobiCom, pp.174-185, Aug. 1999.
[2] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed Diffusion for Wireless Sensor Networking,” IEEE/ACM Transaction on Networking, vol. 11, no. 1, pp. 2-16, Feb. 2003.
[3] P. Ciciriello, L. Mottola, and G. P. Picco, “Efficient Routing from Multiple Sources to Multiple Sinks in Wireless Sensor Networks,” in Proc. of European Work-shop on Wireless Sensor Networks, Jan. 2007.
[4] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Mobile Networks and Applications, vol. 7, issue 6, pp.481-492, Dec. 2002.
[5] J. A. Sanchez, and P. M. Ruiz, "LEMA: Localized Energy-Efficient Multicast Algorithm based on Geographic Routing," in Proc. IEEE LCN, pp.3-12, Nov. 2006.
[6] J. A. Sanchez, P. M. Ruiz, J. Liu, and I. Stojmenovic, “Bandwidth-Efficient Geographic Multicast Routing Protocol for Wireless Sensor Networks,” IEEE Sensor Journal, vol. 7, no.5, pp.627-636, May 2007.
[7] A. Okura, T. Ihara, and A. Miura, “BAM: Branch Aggregation Multicast for Wireless Sensor Networks,” in Proc. of IEEE MASS, Nov. 2005.
[8] A. Okura, T. Ihara, and A. Miura, “Branch Aggregation Multicast (BAM): An Energy Efficient and Highly Compatible Multicast Protocol for Wireless Sensor Networks,” IEICE Transaction on Information and Systems, vol. e89-d, no. 5, pp. 1633-1643, May 2006.
[9] L. Ji, and M. S. Corson, “Differential Destination Multicast-A MANET Multicast Routing Protocol for Small Group,” in Proc. of IEEE INFOCOM, vol. 2, pp. 1192-1202, Apr. 2001.
[10] Network Simulator Version 2 (ns2) Home. http://www.isi.edu/nsnam/ns/
[11] IEEE 802.15.4 Standard Home. http://www.ieee802.org/15/
[12] V. Shnayder, M. Hempstead, B.-r. Chen, G. W. Allen, and M. Welsh, “Simulating the Power Consumption of Large-Scale Sensor Network Applications,” in Proc. of ACM SenSys, pp. 188-200, Nov. 2004.
[13] S. Yamagishi, K. Hitomi, H. Yamanouchi, Y. Yamaguchi, and T. Shibata, “Development and Test of a Compact Lidar for Detection of Oil Spills in Water,” in Proc. of SPIE, pp.136–144, 2000.
[14] H. V. Jensen, J. H. S. Andersen, P. S. Daling, and E. Nost, “Recent Experience from Multiple Remote Sensing and Monitoring to Improve Oil Spill Response Operations,” in Proc. of Int’l Oil Spill Conf, pp. 407-412, 2008.
[15] R. H. Goodman, D. Simecek-Beatty, and D. Hodgins, “Tracking Buoys for Oil Spills,” in Proc. of Int. Oil Spill Conf., pp.3-8, Apr., 1999.
[16] AIS Drift Buoy, http://www.allmaritim.com/english/products/ais-drift-buoy/.
[17] H. Senga, N. Kato, A. Ito, H. Niou, M. Yoshie, I. Fujita, K. Igarashi, and E. Okuyama, “Development of Spilled Oil Tracking Autonomous Buoy System,” in Proc. of MTS/IEEE Oceans, pp. 1-10, Sep. 2007.
[18] N. Kato, M. Hiratsuka, H. Senga, and H. Suzuki, “Spilled Oil Tracking Autonomous Buoy,” in Proc. of IEEE Oceans, pp. 1-9, Sep. 2010.
[19] Y. Huang, W. Liang, H.-B. Lu, and Y. Xiao, “Target Tracking Based on A Distributed Particle Filter in Underwater Sensor Networks,” Wirel. Commun. Mob. Comput., vol. 8 no. 8, pp. 1023-1033, Oct. 2008.
[20] C. M. Kreucher, B. Shapo, and R. Bethel, “Multitarget Detection and Tracking using Multi-Sensor Passive Acoustic Data,” in Proc. of IEEE Aerospace Conf., pp. 1-16, Mar. 2009.
[21] E. Dalberg, A. Lauberts, R. K. Lennartsson, M. J. Levonen, and L. Persson, “Underwater Target Tracking by Means of Acoustic and Electromagnetic Data Fusion,” in Proc. of Int’l Conf. Info. Fusion, pp. 1-7, Jul. 2006.
[22] J. Zhang, T. Yan, J. A. Stankovi, and S. H. Son, “Thunder: Towards practical, Zero Cost Acoustic Localization for Outdoor Wireless Sensor Networks,” ACM SIGMOBILE Mob. Comput. Commun. Review, vol. 11, no. 1, pp. 15-28, Jan. 2007.
[23] Cricket Approach. http://nms.lcs.mit.edu/projects/cricket/.
[24] A. Savvides, C.-C. Han, and M. B. Strivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” in Proc. of ACM MobiCom, pp. 166-179, 2001.
[25] W. D. Wang and Q. X. Zhu, “RSS-based Monte Carlo Localization for Mobile Sensor Networks,” IET Communications, vol. 2, no. 5, pp.673-681, May 2008.
[26] Z. Yang, Y. Liu, and X.-Y. Li, “Beyond Trilateration: On the Localizability of Wireless Ad Hoc Networks,” IEEE/ACM TRANSACTION ON NETWORKING, vol. 18, no. 6, pp.1806-1814, Dec. 2010.
[27] Mica Series Home. http://www.xbow.com.
[28] XSM Series Home. http://cast.cse.ohio-state.edu/exscal.
[29] C. E. Perkins and E.M. Royer, “Ad-hoc On-demand Distance Vector Routing,” in Proc. of IEEE Workshop on Mob. Comput. Syst. Applications, pp. 90-100, Feb. 1999.
[30] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” Mobile Computing (Kluwere Academic Publishers), pp. 153-181, 1996.
[31] B. Hackett, Øyvind Breivik, and C. Wettre, “Forecasting the Drift of Objects and Substances in the Ocean,” Ocean Weather Forecasting: an Integrating View of Oceangraphy, Springer, pp. 507-523, 2006.
[32] Øyvind Breivik and A. A. Allen, “An Operational Search and Rescue Model for the Norwegian Sea and the North Sea,” Journal of Marine Systems, vol. 69, issue 1-2, pp.99-113, Feb. 2008.
[33] E. Anderson, A. Odulo, and M. Spaulding, “Modeling of Leeway Drift,” U.S. Coast Guard Research and Development Center Report, CG-D-06-99, 1998.
[34] A. Caruso, F. Paparella, L. F. M. Vieira, M. Erol, and M. Geria, “The Meandering Current Mobility and Its Impact on Underwater Mobile Sensor Networks,” in Proc. of IEEE INFOCOM, pp.771-779, Apr. 2008.
[35] L. H. Holthuijsen, “Waves in Oceanic and Coastal Waters,” Cambridge University Press, Jan. 2007.
[36] X. Hong, M. Geria, G. Pei, and C. Chiang, “A Group Mobility Model for Ad Hoc Wireless Networks, ” in Proc. of the ACM International Workshop on Modeling and Simulation of Wireless and Mobile Systems, Aug. 1999.
[37] Qualnet Simulator Home. http://www.scalable-networks.com.
[38] X. Ji, H. Zha, J.J. Metzner, and G. Kesidis, “Dynamic Cluster Structure for Object Detection and Tracking in Wireless Ad-hoc Sensor Networks,” in Proc. of IEEE ICC, vol. 7, pp. 3807-3811, Jun. 2004.
[39] W.-R. Chang, H.-T. Lin, and Z.-Z. Cheng, “CODA: A Continuous Object Detection and Tracking Algorithm for Wireless Ad Hoc Sensor Networks,” in Proc. of IEEE CCNC, pp. 168-174, Jan. 2008.
[40] K. M. Low, G. Podnar, S. Stancliff, J. M. Dolan, and A. Elfes, “Robot Boats as a Mobile Aquatic Sensor Network, ” in Proc. of ACM ESSA Workshop, Apr. 2009.
[41] M. Soyturk, and D. T. Altilar, “Reliable Real-Time Data Acquisition for Rapidly Deployable Mission-Critical Wireless Sensor Networks,” in Proc. of IEEE INFOCOM Workshops, pp. 1-6, Apr. 2008.
[42] L. W. Harding, J. G. Kramer, and J. Phinney, “Estuarine and Watershed Monitoring Using Remote Sensing Technology: Present Status and future Trends: a Workshop Report,” Maryland Sea Grant College Publication, 2004.
[43] S. Harchi, J.-P. Georges, and T. Divoux, “WSN Dynamic Clustering for Oil Slicks Monitoring,” in Proc. of Int’l Conf on Wireless Communications in Unusual and Confined Areas (ICWCUCA), pp. 1-6, Apr. 2012.
[44] J. Wang, and Y. Shen, “Modeling Oil Spills Transportation in Seas based on Unstructured Grid, Finite-Volume, Wave-Ocean Model”, Ocean Modeling, vol. 35, Issue 4, pp. 332-344, 2010.
[45] K. Zeng, W. Lou, and H. Zhai, “On End-to-end Throughput of Opportunistic Routing in Multirate and Multihop Wireless Networks,” in Proc. Of IEEE INFOCOM, pp.1490-1498, Apr. 2008.
[46] S. Biswas, and R. Morris, “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” in Proc. of ACM SIGCOMM, pp. 133-143, Aug. 2005.
[47] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading Structure for Randomness in Wireless Opportunistic Routing,” in Proc. of ACM SIGCOMM, Aug. 2007.
[48] K.-C. Chung, H.-C. Chen, and W. Liao, “Congestion-Aware Network-Coding-Based Opportunistic Routing in Wireless Ad Hoc Networks,” in Proc. of IEEE Globecom, 2011.
[49] H. Dubois-Ferrière, “Anypath Routing,” Ph.D dissertation #3636, School of Comput. & Commun. Sci., Ecole Poly-technique Fédérale de Lausanne, Lausanne, Switzerland, Nov. 2006.
[50] H. Dubois-Ferrière, M. Grossglauser, and M. Vetterli, “Valuable Detours: Least-Cost Anypath Routing,” IEEE/ACM TRANSACTIONS ON NETWORKING, vol. 19, no. 2, pp. 333-346, Apr. 2011.
[51] R. Laufer, H. Dubois-Ferrière, and L. Kleinrock, “Polynomial-Time Algorithms for Multirate Anypath Routing in Wireless Multihop Networks,” IEEE/ACM TRANSACTIONS ON NETWORKING, vol. 20, no. 3, pp. 742-755, Jun. 2012.
[52] R. Laufer, P. B. Velloso, L. F. M. Vieira, and L. Kleinrock, “PLASMA: A New Routing Paradigm for Wireless Multihop Networks,” in Proc. Of IEEE INFOCOM, pp. 2706-2710, Mar. 2012.
[53] X. Fang, D. Yang, and G. Xue, “DART: Directional Anyapth Routing in Wireless Mesh Networks,” in Proc. Of IEEE MASS, pp. 590-599, 2011.
[54] X. Fang, D. Yang, and G. Xue, “MAP: Multi-Constrained Anypath Routing in Wireless Mesh Networks,” IEEE TRANSACTIONS ON MOBILE COMPUTING, vol. 12, no. 10, pp. 1893-1906, 2013.
[55] G. Bianchi, and I. Tinnirello, “Kalman Filter Estimation of the Number of Competing Terminals in an IEEE 802.11 Network,” in Proc. Of IEEE INFOCOM, 2003.
[56] G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, vol. 18, no.3, pp.535-547, Mar. 2000.
[57] S. Jain, and S. R. Das, “Exploiting Path Diversity in the Link Layer in Wireless Ad Hoc Networks,” Ad Hoc Netw., vol. 6, no. 5, pp. 805-825, Jul. 2008.
[58] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduce to Algorithms,” The MIT Press 3rd edition, 2009.
[59] G. Bainchi, and I. Tinnirello, “Remarks on IEEE 802.11 DCF Performance Analysis,” IEEE COMMUNICATIONS LETTERS, vol. 9, no. 8, pp.765-767, Aug. 2005.
[60] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959.
[61] G. Barrenetxea, B. Beferull-Lozano, and M. Vetterli, “Lattice Networks: Capacity Limits, Optimal Routing and Queueing Behavior,” IEEE/ACM TRANSACTIONS ON NETWORKINGS, vol. 14, issue 3, pp. 492-505, Jun. 2006.
[62] I. F. Akyildiz, X. Wang, and W. Wang “Wireless Mesh Networks: a Survey,” COMPUTER NETWORKS, vol. 47, issue 4, pp. 445-487, Mar. 2005.
[63] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, “Network Information Flow,” IEEE TRANSACTIONS ON INFORMATION THEORY, Jul. 2000.
[64] WirelessHART Home. http://en.hartcomm.org/
[65] ISA 100.11a Home. http://www.isa100wci.org/
[66] G. Cao, H. Zhang, and L. Li, “A Reliable Multipath Routing Strategy for WirelessHART Mesh Networks Using Subgraph Routing,” Journal of Computational Information Systems, vol. 9, no. 5, pp. 2001-2008, 2013.