臺灣博碩士論文加值系統

在CSMA/CA架構與多重速率、多點跳躍的無線網路環境之下，我們可以藉由根據環境的變化動態調整載波偵聽門檻(carrier-sensing threshold, Tcs)，並進一步平衡空間重複使用率(spatial reuse)及傳輸可靠度(transmission reliability)來達到整體網路效能(network capacity)的最佳化，較低的Tcs會使偵聽範圍(carrier-sensing range, dcs)擴大，而在此情況下能夠經由降低因並行傳輸(concurrent transmissions)造成的封包碰撞以提高資料傳輸的可靠度，然而，整體的網路效能(network capacity)卻會因為節點對於資料傳輸的嘗試太過於保守而下降；反之，較高的Tcs則會使dcs縮小，這樣一來空間重複利用率會得到顯著的提高，但相對的潛在訊號干擾亦會隨著增加而導致封包碰撞更頻繁的發生，因此於建立在CSMA/CA基礎上的無線網路之下根據當下環境情況適當的調節Tcs是非常重要的。在本篇論文中，我們提出一個於分散式的無線環境之下可在合理的計算時間內用以動態調節Tcs之值的適應性機制，模擬結果也證實了我們所提出的演算法所求得的網路效能較其他現有的載波偵聽調節相關演算法要來得佳。

In CSMS/CA-based, multi-hop, multi-rate wireless ad-hoc networks, we can balance the interplay of spatial reuse and transmission reliability by dynamicly tuning carrier-sensing threshold (Tcs) according to environmental situations in order to reach the maximum network capacity. Lower carrier-sensing thresholds generally lead to larger carrier-sensing ranges (dcs), which ensure higher transmission reliability. In this manner, we actually increase the transmission reliability by reducing packet collisions due to mitigated interference produced by concurrent transmissions. However, the total network capacity suffers because of too preservative channel access attempts. On the other hand, higher carrier-sensing thresholds usaually result in smaller carrier-sensing ranges, which encourage better spatial reuse yet transmission collisions will happen more frequently due to potentially increased interference. Therefore, it is important to make adequate adjustments of carrier-sensing thresholds according to environmental conditions in a CSMA/CA-based wireless network. In this thesis, we address the above issue by proposing an adaptive mechanism to dynamicly adjust carrier-sensing thresholds used by wireless nodes in a distributed manner within reasonable computation time. Simulation results show that our proposed algorithm outperforms other implemented carrier-sensing tuning approaches in terms of aggregate network capacity.

摘 要 I
ABSTRACT II
誌 謝 III
目 錄 IV
表 目 錄 VI
圖 目 錄 VII
第 1 章 緒論 1
第 2 章 相關文獻 4
2.1 利用調節載波偵聽門檻(Tcs)實現空間多樣性 4
2.2 利用調節資料傳輸功率(Ptx)實現空間多樣性 5
2.3 其他相關研究 6
2.3.1 LMST-DCUA 8
2.3.2 PCSadapt 9
第 3 章 網路模型與訊號傳播干擾模型 12
3.1 網路模型 12
3.2 訊號傳播干擾模型 12
第 4 章 網路效能方程式推導 16
4.1 Cali’s model 原型及需調整的部分 16
4.2 資料傳輸嘗試機率(Attempt probability, pa)的測定 20
4.3 資料傳輸速率(Data rate)的選定 21
4.4 碰撞區域(Collision Zone, CZ)的定義 23
4.5 網路效能(Network Capacity)的計算 25
第 5 章 網路效能最佳化 29
5.1 最佳化演算法的導入 29
5.1.1 登山演算法(Hill Climbing) 30
5.1.2 模擬退火法(Simulated Annealing) 31
5.1.3 基因演算法(Genetic Algorithm) 33
5.1.4 改良型模擬退火法(Enhanced Simulated Annealing) 35
5.2 理論值計算及分析 37
5.2.1 實例分析-登山演算法(Hill Climbing) 39
5.2.2 實例分析-模擬退火法(Simulated Annealing) 41
5.2.3 實例分析-基因演算法(Genetic Algorithm) 43
5.2.4 實例分析-改良型模擬退火法(Enhanced Simulated Annealing) 45
5.2.5 綜合分析與比較 46
第 6 章 效能評估 51
6.1 ns-2環境參數設定 51
6.2 模擬結果與效能分析 52
6.3 綜合比較 57
第 7 章 結論 80
參 考 文 獻 81

[1] IEEE 802.11a WG Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-speed Physical Layer in the 5 GHz Band, 1999.
[2] A. Akella, G. Judd, P. Steenkiste, and S. Seshan, “Self Management in Chaotic Wireless Deployments”, In Proc. ACM MobiCom, pp. 185-199, Aug. 2005.
[3] P. Bahl, A. Adya, J. Padhye, and A. Wolman, “Reconsidering Wireless Systems with Multiple Radios”, ACM SIGCOMM Computer Communications Review (CCR), 34(5):39-46, Oct. 2004.
[4] P. Bahl, R. Chandra, and J. Dunagan, “SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-hoc Wireless Networks”, In Proc. ACM Int’l Conference Mobile Computing and Networking (MobiCom), pp. 216-230, Sep. 2004.
[5] M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger, “Does Topology Control Reduce Interference ?”, In Proc. ACM MobiHoc, pp. 9-19, May 2004.
[6] F. Cali, M. Conti, and E. Gregori, “Dynamic Tuning of the IEEE 802.11 Protocol to Achieve a Theoretical Throughput Limit”, IEEE/ACM Transactions on Networking, 8(6):785-799, Dec. 2000.
[7] X. Guo, S. Roy, and W. S. Conner, “Spatial Reuse in Wireless Ad-hoc Networks”, In Proc. IEEE VTC, pp. 1437-1442, Oct. 2003.
[8] G. Holland, N. Vaidya, and P. Bahl, “A Rate-adaptive MAC Protocol for Multi-hop Wireless Networks”, In Proc. ACM/IEEE MobiCom, pp. 236-251, Jul. 2001.
[9] K. Jamieson, B. Hull, A. Miu, and H. Balakrishnan, “Understanding the Real-world Performance of Carrier Sense”, In Proc. ACM SIGCOMM, pp. 52-57, Aug. 2005.

[10] T.-S. Kim, H. Lim, and J. C. Hou, “Improving Spatial Reuse Through Tuning Transmit Power, Carrier Sense Threshold, and Data Rate in Multihop Wireless Networks”, In Proc. of ACM MobiCom, pp. 366-377, Sep. 2006.
[11] W. C. Y. Lee, “Elements of Cellular Mobile Radio Systems”, IEEE Transactions on Vehicular Technology, 35(2):48-56, May 1986.
[12] N. Li, J. C. Hou, and L. Sha, “Design and Analysis of an MST-based Distributed Topology Control Algorithm for Wireless Ad-hoc Networks”, IEEE Transactions on Wireless Communications, 4(3):1195-1207, May 2005.
[13] A. Muqattash and M. Krunz, “A Single-channel Solution for Transmission Power Control in Wireless Ad Hoc Networks”, In Proc. ACM MobiHoc, pp. 210-221, May 2004.
[14] R. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment”, In Proc. IEEE INFOCOM, pp. 404-413, Mar. 2000.
[15] T. S. Rappaport, “Wireless Communications: Principles and Practice (Second Edition)”, Upper Saddle River Prentice-Hall, 2002.
[16] J. So and N. Vaidya, “Multi-channel MAC for Ad Hoc Networks: Handling Multi-channel Hidden Terminals Using A Single Transceiver”, In Proc. ACM MobiHoc, pp. 222-233, May 2004.
[17] X. Yang and N. Vaidya, “On Physical Carrier Sensing in Wireless Ad Hoc Networks” In Proc. IEEE INFOCOM, pp. 13-17, Mar. 2005.
[18] H. Zhai and Y. Fang, “Physical Carrier Sensing and Spatial Reuse in Multirate and Multihop Wireless Ad Hoc Networks”, In Proc. IEEE INFOCOM, pp. 1-12, Apr. 2006.


[19] J. Zhu, X. Guo, L. L. Yang, and W. S. Conner, “Leveraging Spatial Reuse in 802.11 Mesh Networks with Enhanced Physical Carrier Sensing”, In Proc. IEEE Int’l Conference Communications (ICC), pp. 4004-4011, Jun. 2004.
[20] Z. Zeng, Y. Yang, and J. Hou, “How Physical Carrier Sense Affects System Throughput in IEEE 802.11 Wireless Networks”, In Proc. IEEE INFOCOM, Alaska, USA, pp. 13-18, Apr. 2008.
[21] K. Park, J. Choi, J. Hou, Y. Hu and H. Lim, “Optimal Physical Carrier Sense in Wireless Networks”, Elsevier Ad Hoc Networks, 9(1):16-27, Jan. 2011.
[22] T.-S. Kim, H. Lim and J. C. Hou, “Understanding and Improving the Spatial Reuse in Multihop Wireless Networks”, IEEE Transactions on Mobile Computing, 7(10):1200-1212, Oct. 2008.
[23] C. Thorpe and L. Murphy, “A Survey of Adaptive Carrier Sensing Mechanisms for IEEE 802.11 Wireless Networks”, IEEE Communications Surveys & Tutorials, 16(3):1266-1291, Mar. 2014.
[24] Y. Z. Liu, X. M. Zhang, Q. Liu, and S. F. Dai, “Interference-aware Physical Carrier Sensing for Maximum Throughput in Ad Hoc Networks”, In Proc. Int’l Conference on Communications and Networking in China, pp. 60-64, Aug. 2008.
[25] B. Alawieh, C. M. Assi, and H. Mouftah, “Investigating the Performance of Power-aware IEEE 802.11 in Multi-hop Wireless Networks”, IEEE Transactions on Vehicular Technology, 58(1):287-300, Jan. 2009.
[26] T.-Y. Lin and J. C. Hou, “Interplay of Spatial Reuse and SINR-determined Data Rates in CSMA/CA-based, Multi-hop, Multi-rate Wireless Networks”, In Proc. IEEE INFOCOM, pp. 803-811, May 2007.
[27] K.-J. Park, L. Y. Kim, and J. C. Hou, “Adaptive Physical Carrier Sense in Topology-controlled Wireless Networks”, IEEE Transactions Mobile Computing, 9(1):87-97, Jan. 2009.


[28] H. Ma, R. Vijayakumar, S. Roy, and J. Zhu, “Optimizing 802.11 Wireless Mesh Networks Based on Physical Carrier Sensing”, IEEE/ACM Transactions on Networking, 17(5):1550-1562, Oct. 2009.
[29] Y. Zhu, Q. Zhang, Z. Niu, and J. Zhu, “On Optimal Physical Carrier Sensing：Theoretical Analysis and Protocol Design”, In Proc. IEEE INFOCOM, pp. 2351-2355, May 2007.
[30] D. Kim and S. Kim, "An Iterative Algorithm for Optimal Carrier Sensing Threshold in Random CSMA/CA Wireless Networks", IEEE Communications Letters, 17(11):2076-2079, Nov. 2013.