氏名　Pham Thanh Giang
学位の種類　博士（工学）
学位記番号　博甲第555号
学位授与の日付　平成22年8月31日
学位論文題目　Fairness and Throughput Improvement for Multi-Hop Wireless Ad Hoc Networks　（マルチホップ無線アドホックネットワークにおける公平性とスループットの向上に関する研究）
論文審査委員
　主査　准教授　中川　健治
　副査　教授　島田　正治
　副査　教授　荻原　春生
　副査　教授　山崎　克之
　副査　准教授　湯川　高志

• 論文目次
• 論文要旨
• 論文審査の結果の要旨

［平成22（2010）年度博士論文題名一覧］ ［博士論文題名一覧］に戻る．

Contents
Table of Contents　p.i
Abstract　p.iv
List of Figures　p.vi
List of Tables　p.ix
List of Abbreviations　p.x
1　introduction　p.1
　1.1　Multi-hop Ad hoc networks　p.1
　1.2　Peformance of multi-hop Ad hoc networks　p.3
2　Architecture of wireless network　p.6
　2.1　IEEE 802.11 standard　p.6
　2.1.1　IEEE 802.11 Physical layer　p.6
　2.1.2　IEEE 802.11 MAC layer　p.8
　2.1.3　Theoretical Maximum Throughput　p.13
　2.2　Radio Propagation Models　p.16
　2.2.1　The Free space model　p.16
　2.2.2　The Two-ray ground reflection model　p.17
　2.2.3　The Shadowing model　p.17
　2.2.4　Types of wireless ranges　p.18
　2.2.5　Quatitative wireless ranges　p.19
　2.3　Ad-hoc routing protocol　p.24
　2.3.1　Highly Dynamic Destination Sequenced Distance Vector Routing　p.24
　2.3.2　Dynamic Source Routing　p.25
　2.3.3　Ad hoc On Demand Distance Vector　p.25
　2.3.4　Temporally Ordered Routing Algorithm　p.26
3　Fairness problems in ad hoc networks　p.28
　3.1　Problems in MAC layer　p.28
　3.1.1　Hidden station problem　p.28
　3.1.2　Extended Inter-Frame Space problem　p.29
　3.1.3　Three-pair scenario problem　p.31
　3.2　Problems in Link layer　p.33
　3.2.1　Problems in FIFO Scheduling　p.33
　3.2.2　Problems in RR Scheduling　p.35
　3.3　Related Work　p.37
　3.3.1　Li's proposal　p.37
　3.3.2　Jun's proposal　p.38
　3.3.3　Shagdar's proposal　p.41
　3.3.4　Izumikawa's proposal　p.43
4　Probabilistic Control on Round robin Queue scheduling　p.46
　4.1　Instruction　p.46
　4.2　Related Work　p.47
　4.3　Probabilistic Control on Round robin Queue Scheduling　p.49
　4.3.1　Algorithm 1 （ Controlling the number of input packets to queues ）　p.49
　4.3.2　Algorithm 2 （ Controlling the turn of reading queues ）　p.50
　4.3.3　Algorithm 3 （ Controlling the number of output packets from queues ）　p.50
　4.4　Performance Evaluation　p.51
　4.4.1　Scenario-1　p.52
　4.4.2　Scenario-2　p.56
　4.4.3　Scenario-3　p.59
　4.4.4　Scenario-4　p.60
　4.5　Discussion on parameter values　p.62
　4.6　Summary　p.62
5　Cross-layer based on Utilization evaluation to Contention Window Adaptation method　p.64
　5.1　Introduction　p.64
　5.2　Related Work　p.66
　5.3　Cross-layer based on Utilization evaluation to Contention Window adaption mathod　p.68
　5.3.1　CS Flow Estimation module　p.68
　5.3.2　TX Flow Estimation module　p.69
　5.3.3　Utilization Esitimation module　p.70
　5.3.4　Queue Estimation module　p.70
　5.3.5　CW Monitor module　p.71
　5.3.6　Module Set I　p.72
　5.3.7　Module Set II　p.72
　5.4　Performance Evaluation　p.73
　5.4.1　Scenario-1: The large-EIFS topology　p.74
　5.4.2　Scenario-2: The three-pair topology　p.77
　5.4.3　Scenario-3: The long station chain topology　p.79
　5.4.4　Scenario-4: The grid topology　p.80
　5.4.5　Scenario-5: The random topology　p.82
　5.4.6　Scenario-6: The dynamic number of flows and the dynamic offered loads　p.83
　5.5　Summary　p.85
6　Conclusion and Future Work　p.86
　6.1　Discussion in Fairness　p.86
　6.2　Discussion in Utilization　p.87
　6.3　Compairision between PCRQ scheduling and CUCW method　p.88
　6.4　Conclusions　p.88
　6.5　Future Work　p.89
Appendix　p.89
　Appendix A:Definition of per-flow fairness　p.90
Acknowledgment　p.90
Bibliography　p.91

　Multi-hop wireless networks have become increasingly popular. They provide a fast and easy way to establish a new network in areas where the infrastructure cannot be established. The advantage of a wireless network is the mobility and freedom from the restriction of wires or a fixed connection. It is simply two or more computers linked together by invisible radio waves with the purpose of transferring data or sharing resources. However, there are many complex techniques behind it and there is ample scope for its improvement areas of Quality of Service （QoS）.

　In this thesis, the architecture of the wireless network is studied, such as ad-hoc routing protocols, Medium Access Control （MAC） layer and Physical Layer （PHY） in the wireless network. Then their effect to the performance of wireless networks is pointed out. Among the components of the wireless network, the IEEE 802.11 standard is the most important; it includes the principle of operations for both MAC and PHY layer. However, the IEEE 802.11 standard, the de facto standard for wireless ad hoc network, does not perform well in terms of delay, throughput, and specially, fairness in multi-hop wireless ad hoc networks. The fairness problems in multi-hop wireless ad-hoc networks based on the IEEE 802.11 standard environment are focused and two new methods are proposed to solve those problems.

　First, a new scheduling method, Probabilistic Control on Round robin Queue （PCRQ） scheduling is proposed to achieve per-flow fairness in multi-hop ad hoc networks. PCRQ scheduling is put at the link layer, so it is not necessary to modify IEEE 802.11 MAC protocol. PCRQ scheduling achieves good performance results in both UDP and TCP traffic. In PCRQ scheduling, a new link layer scheduling is proposed without assuming the fairness of the MAC layer. The Round Robin （RR） queues are applied in the link layer, and three algorithms are proposed to control the number of input packets to the queue, the turn of reading queues, and the number of output packets from the queue. PCRQ scheduling can improve indirectly the MAC layer fairness by these algorithms in the link layer. It does not modify the IEEE 802.11 MAC layer protocols. In addition to per-flow fairness, PCRQ scheduling archives positive impact in terms of the effective buffer resource and delay time. The efficiency of PCRQ scheduling is evaluated in NS-2 network simulator by comparing with the FIFO scheduling, RR scheduling, and Shagdar’s method on various topologies of multi-hop ad hoc networks. The results show that PCRQ scheduling achieves the best fairness index, the smallest queue length and the smallest delay time in all methods.

　Second, Cross-layer method based on the Utilization evaluation for Contention Window adaptation （CUCW） is proposed for fairness performance. While PCRQ scheduling works only in the link layer, CUCW method requires a minor modification to the physical, MAC and link layers. Because PCRQ scheduling works in the link layer, it cannot solve all unfairness problems between flows at the MAC layer. Thus, CUCW method is necessary to touch lower layers in order to achieve better results. In CUCW method, five modules are proposed in the physical, MAC and link layers. CS Flow Estimation module is put at the physical layer to sense whether some flows are being transmitted in the carrier sensing range but out of the transmission range of the station. TX Flow Estimation module is put at the MAC layer to classify the flows which are being transmitted in the transmission range of the station. Utilization Estimation module is put at the MAC layer to measure the current link utilization. Queue Estimation module is put at the link layer to evaluate the contention between flows in the buffer space. The last CW Monitor module is put at the MAC layer to decide a good CW size for achieving fair bandwidth allocation between stations and between flows in the station based on the information collected from above four modules. Performance of CUCW method is examined by using NS-2. The results show that CUCW method achieves good performance in both fairness and throughput on various asymmetric multi-hop network topologies such as large-EIFS problem, three-pair problem scenarios and also complex asymmetric topologies as long-station chain, grid, random and dynamic topologies.

　本論文は，マルチホップ無線アドホックネットワークにおけるサービス品質として重要な，各フローのスループットの公平性とトータルスループットの向上を目的として新たなパケット制御アルゴリズムを提案するものであり，6章からなる。

　第1章では，マルチホップ無線アドホックネットワークの概要を説明している。

　第2章では，無線ネットワークのアーキテクチャの技術的な詳細について述べている。

　第3章では，アドホックネットワークにおいて公平性が達成されない様々な問題点について詳細に検討している。

　第4章では，フロー毎のスループットの公平性を実現する第1の方法として，PCRQ（Probabilistic Control on Round robin Queue，ラウンドロビンキューの確率的制御）スケジューリングを提案している。Link層において3つのパケット制御アルゴリズムが提案されている。1つ目のアルゴリズムによって大きな負荷のフローからのパケットを減少させることができ，2つ目のアルゴリズムによって小さな負荷のフローからのパケットにより多く送信機会を与え，3つ目のアルゴリズムによって大きな負荷のフローからのパケットをMAC層から送信するのを少なくしてその帯域をパケット受信に使う。それによって帯域の公平な割り当てを実現している。このようにして，PCRQスケジューリングは，IEEE802.11 MAC層のプロトコルを変更することなくMAC層の公平性を改善し，さらにフロー毎の公平性を達成している。この点において従来の研究には無い独創的で実用的な研究成果である。

　第5章では，第2の方法として，CUCW（Cross-layer based on Utilization evaluation to Contention Window adaptation method，輻輳窓の適応制御に基づいたクロスレイヤパケット制御方式）を提案している。Link層でのみ動作するPCRQと異なり，CUCWでは，物理層，MAC層，Link層の情報を統合して動作する。そのことによって，スループットとその公平性の向上，特にフロー毎の高い公平性が得られる。新たに5つのモジュールが提案され，それらは，物理層，MAC層，Link層で動作する。4つのモジュールによって，伝送範囲外のフロー数，伝送範囲内のフロー数，リンク利用率，キュー長の方法を収集し，1つのモジュールで輻輳窓サイズを決定する。決定された輻輳窓サイズに基づいて，より多くのパケットを転送するフローのパケットの優先度を下げ，少ないフローのパケットの優先度を上げることによってパケット転送量の公平性を達成している。特に，収集した情報の意味を有効に利用して輻輳窓サイズをパケット毎に調整している点に優れた新規性がある。本提案方式を計算機シミュレーションによって評価し，従来法よりも優れた特性が得られることを確認している。

　最終の第6章で結論と今後の課題について述べている。

　以上の内容から，本論文は工学上および工業上貢献するところが大きく博士（工学）の学位論文として十分な価値を有するものと認める。