封包傳輸的碰撞問題，一直是感測網路中網路層與媒體存取控制層的主要研究課題之一。在無線感測器網路中，重新排程為嶄新的研究領域。然而重新排程的方法，尚有眾多的細節與挑戰待進一步研究。本論文包含了感測網路中局部重新排程的分析，並提出了數個局部重新排程的演算法。文中針對這些演算法，評量出碰撞比率降低的程度。所有局部重新排程的解決方案，必須要能保證網路在局部重新排程之後，仍然能維持整體網路的連通性。考慮新的節點進入無線感測網路的情況，本論文推導出最大網路鄰居數改變後的理論上限值。配合了實際環境參數模擬，理論與實際的落差闡述了現有解決方法的缺點，成為演算法設計的動機。論文中共提出了兩個鏈路排程與一個廣播排程演算法，在已經被排程的網路中，考慮了週期長度、排程需求量與現有負載程度對重新排程之影響。相比於現有的做法，在不造成網路連通性的斷裂下，本篇論文提出的演算法，模擬結果大幅提升了局部重新排程的成功率。於鏈路排程可提高30%以上的排程成功率；在廣播排程之排程在週期夠長的情況下，能提高排程成功率至接近90%。若將排程限制降低到只要確保網路的連通性不會斷裂，並有足夠的現有排程負載，鏈路排程亦可接近100%的排程成功率。
在水下感測器網路中，不穩定的連接鏈路以及水中環境的特性與陸地上之差異，上述局部重新排程的方法，將不再適合水下感測器網路之網路層與媒體存取控制層。鑒於水下間斷的連接鏈路之特性，現有的陸地上基於訊息傳送的方式、或以同步為基礎的作法，均無法達到令人滿意的封包傳送成功率。於水下感測網路中，由於感測器具有無法即時充電的特性，所以能量消耗更是需要嚴加控管。為了研究水下封包傳輸的碰撞情形，論文中對水下感測網路中，任意兩組傳輸封包碰撞的機率提出了數學理論上的分析，而模擬的實驗結果也同時驗證了理論的分析成果。從以上的研究，得到水下感測網路的封包碰撞機率是偏低的。由於較高的頻寬及水中較慢的介質速度，水底下的封包碰撞的機率大幅降低至10% 以下。根據這項重大的發現，本論文提出了一個特別適用於水中環境的低延遲省電網路繞徑協定 (DEEP) 。DEEP採用了真實感測器的參數來設計能量消耗模型，並包含了一個動態的代傳點選擇機制。此選擇機制考慮了不同傳輸距離及載波頻率下，傳輸過程中能量使用的效率以及可用之頻寬。模擬結果顯示出DEEP不需要額外的碰撞偵測機制，即可花費較少的能量得到較高的封包傳輸成功率。在網路鏈路品質極度不佳的情形下，更能發揮此演算法的優點。在只有20%傳送成功機會的惡劣的網路品質情況下，與現有的做法相比，相近的能量消耗卻能有效的降低30% 端到端的延遲時間，並同時提昇20%的封包傳送成功率。這些結果確保了DEEP能有效的面對封包碰撞問題所帶來的挑戰。

The collisions of packet transmissions in sensor networks have been one of the main topics in MAC/Protocol layers. In wireless sensor networks, among all the solutions to the packet interferences, rescheduling has a potential to be a profitable solution which has abundant issues yet to be explored. The local rescheduling problem in wireless sensor networks has been firstly addressed and investigated in the thesis. The algorithms of local rescheduling have been proposed and evaluates the performance of reschedule solutions with different metrics.
All solutions have to be under the limitation that the network should stay connected after the process of rescheduling. This thesis introduces a theoretical bound of maximum degree after node insertion. Along with empirical results in real world settings, the results motivate the
design of algorithms and give possible reasons why existing rescheduling algorithms do not work efficiently. Two local link rescheduling algorithms and one local broadcast rescheduling algorithm are developed as improvements. Consider different cycle lengths, slot requests, and occupied slot number with different node densities and other critical parameters, simulations show that the developed algorithms greatly improve the ratio of finding proper solutions successfully in both types of scheduling compared with existing simple algorithms. Without breaking the network connectivity, 30% of successful rate is increased in link scheduling; 90% of successful ratio can be reached if the cycle length of the scheduling is long enough in broadcast scheduling. If the prescheduled network has sufficient occupied slots to release to the new node, nearly 100% of successful rate of rescheduling can be accomplished if the limitation is relaxed, where only network connectivity is guaranteed.
Due to the unstable link connectivity and different characteristics in acoustic channel in underwater sensor networks, the scheme of local rescheduling is no longer beneficial to the design of the MAC/Protocol layers in underwater sensor networks. Given the properties of intermittent link connectivity in USNs, the existing message-based and synchronization-based approaches cannot meet packet delivery requirements. In recent years, a specific field of three-dimensional (3D) underwater sensor networks (USNs) have received substantial attention as a promising tool for target tracking and remote monitoring under the seas. Energy consumption is crucial in USNs since it is nearly impossible to recharge the batteries of the sensors. To deal with the collision issue and further reduce the energy consumption, an analysis for the probability of collisions between any two transmissions in USNs is presented in the thesis, in which the analyzed collision rate corresponds to the simulation and is demonstrated to be relaxed with a sufficient data processing rate in underwater networks. Under 10% of packet collision rate is found due to higher bandwidth and lower propagation speed in the water. Based on this result, a tailored delay-aware energy-efficient routing protocol (DEEP) is proposed for USNs. DEEP is composed of an energy model with realistic parameters in which the available 3dB bandwidth is derived with respect to the distances between nodes. DEEP involves an adaptable forwarding node selection mechanism, which incorporates the concept of energy efficiency and further reduces the collision rate. Simulations show that DEEP expends less
energy for higher successful packet delivery compared with previous studies. Benefits from the higher bandwidth in USNs, DEEP reduces the collision occurrences and elevates 20% of the packet delivery ratio with the reduction of 30% of end-to-end delay time especially when the network conditions are unfavorable with average 20% of link quality. These results confirm that DEEP effectively handles the challenges.

[1] S. Ravindran and P. Narayanasamy, “EnergyAware
Face Geocast for Wreless Adhoc and
Sensor Networks,” International Conference on Electronics Computer Technology, vol. 1,
pp. 6–10, Apr. 2011.
[2] S. K. Dhurandher, M. S. Obaidat, and M. Gupta, “A Novel Geocast Technique with
Hole Detection in Underwater Sensor Networks,” IEEE/ACS International Conference on
Computer Systems and Applications, pp. 1–8, May 2010.
[3] A. Chen, S.Kumar, and T. H. Lai, “Designing Localized Algorithms for Barrier Coverage,”
ACM International Conference on Mobile Computing and Networking, pp. 63–74, 2007.
[4] C. H. Yang and K. F. Ssu, “An Energyefficient
Routing Protocol in Underwater Sensor
Networks,” International Conference on Sensing Technology, pp. 114–118, Dec. 2008.
[5] Y. S. Chen, Y.W. Lin, and S. L. Lee, “A Mobicast Routing Protocol in Underwater Sensor
Networks,” IEEE Wireless Communications and Networking Conference, pp. 510–515,
Mar. 2011.
[6] I. F. Akyildiz, D. Pompili, and T. Melodia, “Underwater Acoustic Sensor Networks:
Research Challenges,” Ad Hoc Networks (Elsevier), vol. 3, no. 3, pp. 257–279, Feb. 2005.
[7] S. Ramanathan and E. L. Lloyd, “Scheduling Algorithms for Multihop Radio Networks,”
Transactions on Networking, vol. 1, no. 2, pp. 166–177, Apr. 1993.
[8] C. Wang and K. F. Ssu, “A Distributed CollisionFree
LowLatency
Link Scheduling
Scheme in Wireless Sensor Networks,” Wireless Communications and Networking Conference,
pp. 1–6, Apr. 2010.
[9] E. M. Sozer, M. Stojanovic, and J. G. Proakis, “Underwater Acoustic Networks,” IEEE
Journal of Oceanic Engineering, vol. 25, no. 1, pp. 72–83, Jan. 2000.
[10] D. Green, J. A. Rice, and S. Merriam, “Implementing an Undersea Wireless Network
Using Cots Acoustic Modems,” International Conference on Marine Technology Society
Ocean Community, pp. 1027–1031, 1998.
[11] E. Cayirci, H. Tezcan, Y. Dogan, and V. Coskun, “Wireless Sensor Networks for Underwater
Surveillance systems,” Ad Hoc Networks, vol. 4, no. 4, pp. 431–446, Dec. 2006.
[12] E. Kim, J. Kang, P. K. Chong, S. Yoo, and D. Kim, “Energy Efficient Local Area Source
Routing Protocol of Underwater Sensor Networks in the Deep Ocean,” Symposium on
Communications and Information Technologies, pp. 948–953, Aug. 2007.
[13] I. Vasilescu, K. Kotay, D. L. Rus, M. Dunbabin, and P. Corke, “Data Collection, Storage,
and Retrieval with an Underwater Sensor Network,” International conference on
Embedded Networked Sensor Systems, Nov. 2005.
[14] H. J. Yao and G. S. Kuo, “On the Design of Energyefficient
Routing Protocols in Underwater
Networks,” Sensor, Mesh and Ad Hoc Communications and Networks, pp. 80–90,
June 2007.
[15] V. Ravelomanana, “Extremal Properties of ThreeDimensional
Sensor Networks with
Applications,” IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 246–257, July
2004.
[16] J. Partan, J. Kurose, and B. N. Levine, “A Survey of Practical Issues in Underwater
Networks,” ACM International Workshop on Underwater Networks, pp. 17–24, 2006.
[17] X. Guo, M. Frater, and M. Ryan, “Design of a PropagationDelayTolerant
MAC Protocol
for Underwater Acoustic Sensor Networks,” IEEE Journal of Oceanic Engineering,
vol. 34, no. 2, pp. 170–180, 2009.
[18] D. Pompili and I. F. Akyildiz, “Overviewof Networking Protocols for UnderwaterWireless
Communications,” IEEE Communications Magazine, vol. 47, no. 1, pp. 97–102, 2009.
[19] Z. xin Feng and K. W. Chin, “A Survey of Delay Tolerant Networks Routing Protocols,”
Computing Research Repository, vol. abs/1210.0965, Nov. 2012.
[20] R. J. Urick, Principles of Underwater Sound. Sage Publicaiotns, 1983.
[21] W. Zhang and U. Mitra, “A DelayReliability
Analysis for Multihop Underwater Acoustic
Communication,” ACM International Workshop on Underwater Networks, pp. 57–64,
Sept. 2007.
[22] A. Sehgal, C. David, and J. Schonwalder, “Energy Consumption Analysis of Underwater
Acoustic Sensor Networks,” MTS/IEEE OCEANS Conference, pp. 1–6, Sept. 2011.
[23] Z. Peng, Y. Zhu, Z. Zhou, Z. Guo, and J. H. Cui, “COPEMAC:
A Contentionbased
Medium Access Control Protocol with Parallel Reservation for Underwater Acoustic
Networks,” MTS/IEEE OCEANS Conference, pp. 1–10, May 2010.
[24] N. Chirdchoo, W. S. Soh, and K. C. Chua, “AlohaBased
MAC Protocols with Collision
Avoidance for Underwater Acoustic Networks,” INFOCOM IEEE International Conference
on Computer Communications, pp. 2271–2275, May 2007.
[25] W. Chen and U. Mitra, “Packet Scheduling for Multihopped Underwater Acoustic Communication
Networks,” MTS/IEEE OCEANS Conference, pp. 1–6, Oct. 2007.
[26] Z.Wu, C. Tian, H. Jiang, andW. Liu, “MinimumLatency
Aggregation Scheduling in UnderwaterWireless
Sensor Networks,” IEEE International Conference on Communications,
pp. 1–5, June 2011.
[27] A. Pantelidou and A. Ephremides, “Scheduling in Wireless Networks,” Foundations and
Trends in Networking, vol. 4, no. 4, pp. 421–511, Apr. 2011.
[28] G. S. Ahn, S. G. Hong, E. Miluzzo, A. T. Campbell, and F. Cuomo, “FunnelingMAC:
A
Localized, SinkOriented
MAC for Boosting Fidelity in Sensor Networks,” International
Conference on Embedded Networked Sensor Systems, pp. 293–306, Oct. 2006.
[29] W. Z. Wang, Y. Wang, X. Y. Li, W. Z. Song, and O. Frieder, “Efficient InterferenceAware
TDMA Link Scheduling for Static Wireless Networks,” International Conference
on Mobile Computing and Networking, pp. 262–273, 2006.
[30] W. Ye, J. Heidemann, and D. Estrin, “An EnergyEfficient
MAC Protocol for Wireless
Sensor Networks,” International Conference on Computer Comunications, pp. 1567–
1576, June 2002.
[31] J. Yackoski and C. C. Shen, “UWFLASHR:
Achieving High Channel Utilization in a
Timebased
Acoustic MAC Protocol,” International Workshop on Underwater Networks,
pp. 59–66, 2008.
[32] S. Ramanathan, “A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment
inWireless Networks,” Joint Conference of the IEEE Computer and Communications
Societies, vol. 2, pp. 900–907, Apr. 1997.
[33] E. Hossain and V. K. Bhargava, “A Centralized TDMAbased
Scheme for Fair Bandwidth
Allocation inWireless IP Networks,” IEEE Journal on Selected Areas in Communications,
vol. 19, no. 11, pp. 2201–2214, Nov. 2001.
[34] I. Rhee, A. Warrier, J. Min, and L. Xu, “DRAND: Distributed Randomized TDMA
Scheduling for Wireless Ad Hoc Networks,” IEEE Transactions on Mobile Computing,
vol. 8, no. 10, pp. 1384–1396, Oct. 2009.
[35] M. H. Ammar and D. S. Stevens, “A Distributed TDMA Rescheduling Procedure for
Mobile Packet Radio Networks,” IEEE International Conference on Communications,
vol. 3, pp. 1609–1613, June 1991.
[36] E. Arikan, “Some Complexity Results about Packet Radio Networks,” IEEE Transactions
on Information Theory, vol. 30, pp. 681–685, 1984.
[37] S. Even, O. Goldreich, S. Moran, and P. Tong, “On the NPCompleteness
of Certain
Network Testing Problems,” Networks, vol. 14, no. 1, pp. 1–24, 1984.
[38] A. Ephremides and T. V. Truong, “Scheduling Broadcasts in Multihop Radio Networks,”
IEEE Transactions on Communications, vol. 38, no. 4, pp. 456–460, Apr. 1990.
[39] K. M. Anstreicher, “The Thirteen Spheres: A New Proof,” Discrete and Computational
Geometry, vol. 31, pp. 613–625, Mar. 2004.
[40] T. C. Hales, “An Overview of the Kepler Conjecture,” IEEE Communications Magazine,
vol. 44, pp. 115–121, Apr. 2002.
[41] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups. Springer,
third ed., 1999.
[42] K. Sch¨utte and B. L. van derWaerden, “Das Problem der dreizehnKugeln,” Mathematische
Annalen, vol. 125, pp. 325–334, Apr. 1953.
[43] J. Leech, “The Problem of Thirteen Spheres,” The Mathematical Gazette, pp. 22–23, Feb.
1956.
[44] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups. Springer,
third ed., 1999.
[45] K. Kredo II and P. Mohapatra, “Scheduling Granularity in Underwater Acoustic Networks,”
Proceedings of ACM International Workshop on Underwater Networks, pp. 1–8,
2011.
[46] K. Kredo, P. Djukic, and P. Mohapatra, “STUMP: Exploiting Position Diversity in the
Staggered TDMA Underwater MAC Protocol,” INFOCOM IEEE International Conference
on Computer Communications, pp. 2961–2965, Apr. 2009.
[47] X. X. Guo, M. Frater, and M. Ryan, “A Propagationdelaytolerant
Collision Avoidance
Protocol for Underwater Acoustic Sensor Networks,” MTS/IEEE OCEANS Conference,
pp. 1–6, May 2006.
[48] M. Molins and M. Stojanovic, “Slotted FAMA: AMAC Protocol for Underwater Acoustic
Networks,” MTS/IEEE OCEANS Conference, pp. 1–7, May 2006.
[49] P. Karn, “MACA A
New Channel Access Method for Packet Radio,” Proceedings of
ARRL Amateur Radio Computer Networking Conference, pp. 1–5, Sept. 1990.
[50] H. H. Ng,W. S. Soh, and M. Motani, “MACAU:
AMedia Access Protocol for Underwater
Acoustic Networks,” IEEE GLOBECOM Global Telecommunications Conference, pp. 1–
5, Dec. 2008.
[51] S. Climent, N. Meratnia, and J. Capella, “Impact Analysis of Different Scheduling and
Retransmission Techniques on an Underwater Routing Protocol,” Proceedings of ACM
International Workshop on Underwater Networks, pp. 1–8, Dec. 2011.
[52] Y. Ma, Z. Guo, Y. Feng, M. Jiang, and G. Feng, “CMAC:
A TDMABased
MAC Protocol
for Underwater Acoustic Sensor Networks,” International Conference on Networks
Security, Wireless Communications and Trusted Computing, pp. 728–731, Apr. 2009.
[53] D. Pompili, T. Melodia, and I. F. Akyildiz, “A CDMAbased
Medium Access Control for
Underwater Acoustic Sensor Networks,” IEEE Transactions onWireless Communications,
vol. 8, no. 4, pp. 1899–1909, Apr. 2009.
[54] D. Pompili, T. Melodia, and I. F. Akyildiz, “Routing Algorithms for DelayInsensitive
and DelaySensitive
Applications in Underwater Sensor Networks,” ACM Conference on
Mobile Computing and Networking, pp. 298–309, Sept. 2006.
[55] S. Lee, B. Bhattacharjee, and S. Banerjee, “Efficient Geographic Routing in Multihop
Wireless Networks,” ACM Conference on Mobile Ad Hoc Networking and Computing,
pp. 230–241, May 2005.
[56] K. Zeng,W. Lou, J. Yang, and D. R. Brown, “On Geographic Collaborative Forwarding in
Wireless Ad Hoc and Sensor Networks,” International Conference onWireless Algorithms,
Systems and Applications, pp. 11–18, Aug. 2007.
[57] “The Woods Hole Oceanographic Institution MicroModem.”
http://acomms.whoi.edu/umodem/.
[58] B. Tomasi, D. Munaretto, J. C. Preisig, and M. Zorzi, “Realtime
Redundancy Allocation
for Timevarying
Underwater Acoustic Channels,” Proceedings of ACM International
Conference on Underwater Networks and Systems, pp. 1–7, 2012.
[59] H. Yang, B. Liu, F. Ren, H. Wen, and C. Lin, “Optimization of Energy Efficient Transmission
in Underwater Sensor Networks,” Proceedings of IEEE Conference on Global
Telecommunications, pp. 1193–1198, 2009.
[60] R. Srivastava and C. E. Koksal, “Energy Optimal Transmission Scheduling in Wireless
Sensor Networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 5,
pp. 1550–1560, May 2010.
[61] Z. Zhou, Z. Peng, J. H. Cui, and Z. Shi, “Efficient Multipath Communication for TimeCritical
Applications in Underwater Acoustic Sensor Networks,” IEEE/ACMTransactions
on Networking, vol. 19, no. 1, pp. 28–41, Feb. 2011.
[62] S. Biswas and R. Morris, “ExOR: Opportunistic Multihop
Routing for Wireless Networks,”
International Conference on Applications, Technologies, Architectures, and Protocols
for Computer Communications, pp. 133–144, Aug. 2005.
[63] H. D. Ferriere, M. Grossglauser, and M. Vetterli, “LeastCost
Opportunistic Routing,”
pp. 1–8, Sept. 2007.
[64] N. Nicolaou, A. See, J. H. Cui, and D. Maggiorini, “Improving the Robustness of LocationBased
Routing for Underwater Sensor Networks,” MTS/IEEEOCEANSConference, pp. 1–
6, June 2007.
[65] M. Zorzi and R. R. Rao, “Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor
Networks: Energy and Latency Performance,” IEEE Transactions on Mobile Computing,
vol. 2, no. 4, pp. 349–365, Oct. 2003.
[66] J. M. Jornet, M. Stojanovic, and M. Zorzi, “Focused Beam Routing Protocol for Underwater
Acoustic Networks,” Workshop on UnderWater Networks, pp. 75–82, Sept. 2008.
[67] H. Yan, Z. J. Shi, and J. H. Cui, “DBR: Depthbased
Routing for Underwater Sensor
Networks,” IFIPTC6
Networking Conference on AdHoc and Sensor Networks, Wireless
Networks, Next Generation Internet, pp. 72–86, May 2008.
[68] D. Hwang and D. Kim, “DFR: Directional Floodingbased
Routing Protocol for Underwater
Sensor Networks,” MTS/IEEE OCEANS Conference, pp. 1–7, Sept. 2008.
[69] U. Lee, P. Wang, Y. Noh, L. F. M. Vieira, M. Gerla, and J. H. Cui, “Pressure Routing for
Underwater Sensor Networks,” International Conference on Computer Communications,
pp. 1–9, Mar. 2010.
[70] L. Vieira, “Performance and Tradeoffs
of Opportunistic Routing in Underwater Networks,”
International Wireless Communications and Networking Conference, pp. 2911–
2915, Apr. 2012.
[71] F. Fazel, M. Fazel, and M. Stojanovic, “Random Access Compressed Sensing for EnergyEfficient
Underwater Sensor Networks,” IEEE Journal on Selected Areas in Communications,
vol. 29, no. 8, pp. 1660–1670, Sept. 2011.
[72] B. Jalving, “Depth Accuracy in Seabed Mapping with Underwater Vehicles,” MTS/IEEE
OCEANS Conference, pp. 973–978, Sept. 1999.
[73] L. M. Brekhovskikh and Y. Lysanov, Fundamentals of Ocean Acoustics. AIP
Press/Springer, 2003.
[74] R. F. Coates, Underwater Acoustic Systems. John Wiley, 1989.
[75] J. M. Jornet and M. Stojanovic, “Distributed Power Control for Underwater Acoustic
Networks,” MTS/IEEE OCEANS Conference, pp. 1–7, Sept. 2008.
[76] E. Gallimore, J. Partan, I. Vaughn, S. Singh, J. Shusta, and L. Freitag, “The WHOI
Micromodem2:
A Scalable System for Acoustic Communications and Networking,”
MTS/IEEE OCEANS Conference, pp. 1–7, Sept. 2010.
[77] “The Network Simulator ns2.”
http://www.isi.esu/nsnam/ns/.
[78] A. F. Harris and M. Zorzi, “Modeling the Underwater Acoustic Channel in ns2,” Proceedings
of International Conference on Performance Evaluation Methodologies and Tools,
Oct. 2007.
[79] L. Freitag, M. Grund, S. Singh, J. Partan, P. Koski, and K. Ball, “The WHOI MicroModem:
An Acoustic Communications and Navigation System for Multiple Platforms,”
MTS/IEEE OCEANS Conference, pp. 1086–1092, Sept. 2005.
[80] S. Singh, S. E. Webster, L. Freitag, L. L. Whitcomb, K. Ball, J. Bailey, and C. Taylor,
“Acoustic Communication Performance of the WHOI MicroModem
in Sea Trials of the
Nereus Vehicle to 11,000 m Depth,” MTS/IEEE OCEANS Conference, pp. 1–6, Oct. 2009.