九州大学学術情報リポジトリ
Kyushu University Institutional Repository
無線バックホールシステムにおける多段無線中継
金, 光日
Graduate School of Information Science and Electrical Engineering, Kyushu University
https://doi.org/10.15017/21680
出版情報：九州大学, 2011, 博士（工学）, 課程博士 バージョン：
権利関係：
無線バックホールシステムにおける 多段無線中継
金 光日
平成 24 年 2 月
概要 i
概要
次世代ブロードバンド無線通信に求められる数百 Mbps の伝送レートを実現す るためには、守備半径が数十メートルの狭小セル基地局（スモールセル基地局）
を多数敷設することが必要となる。スモールセル基地局の敷設コスト削減は次 世代ブロードバンド無線通信を実現する鍵と言っても過言ではない。この目的 のため、スモールセル基地局を無線で多段中継接続するセルラシステムが検討 されている。基地局群のうち幾つか（コアノード）を有線で基幹網へと接続し、
その他（スレーブノード）はコアノードを介した多段無線中継により基幹網と 接続される。基地局と基幹網を接続するための有線回線の敷設数を削減できる ため、システム全体の敷設コストを低減することができる。また基地局が有線 で縛られないため、基地局の再配置や追加が楽に行える利点も有する。当該無 線中継網は通称、無線バックホールと呼ばれている。無線中継可能な段数が多 ければ多いほど、システムの敷設に必要な有線回線の敷設量を削減できる。ま た欧州などで数多く現存する歴史的建造物等の一部の建物における無線エリア 構築では、有線回線の敷設が不可能な場合があり、無線中継可能な段数が多け れば多いほど、当該無線システムの適用可能範囲を拡大することができる。す なわち許容可能な無線中継段数は、無線バックホールの性能を測るもっとも重 要な指標である。
多段無線中継を阻害する最大の課題は電波干渉である。我々の研究室では無 線バックホールおいて多段無線中継を高効率に行う手法として、周期的間欠送 信法（IPT：Intermittent Periodic Transmission）を提案している。IPT は、
パケットの送信源となるノードにおいて一定の送信周期（IPT 送信周期）を持っ て間欠的に送信することにより、中継経路上での同一周波数リユース間隔を調
概要 ii
整し、最適な送信周期を設定することで電波干渉によるパケット衝突を回避す ることを特徴とする。IPT による中継伝送効率の改善効果は実証実験によっても 確認されており、10 段以上の多段中継も可能であることが実機上で示されてい る。本論文では IPT によりもたらされた多段無線中継の性能を更に向上させる ため、３つの研究について取り組んだ。
第一の研究は、安定した IPT の運用を保証するための中継経路の安定性改善 である。IPT はツリー構造の中継経路上で運用され、中継経路の設定（ルーティ ング）は IPT の伝送性能を大きく左右する。無線バックホールシステムでは各 基地局は固定的に設置されるため、基地局間の伝搬路特性は変動しないものと 誤解される場合があるが、実際には人の移動やドアの開閉等によって変動する。
従来のルーティング手法では、無線伝搬路特性の時間変動を考慮しておらず、
経路を構築した瞬間の伝搬路特性によって構築された中継経路は、それ以降も 最適である保証はない。動的な伝搬路特性の変動に追随しようと、ルーティン グを繰り返すと、中継経路が不安定となってしまう。本論文では無線伝搬路特 性が時間変動する環境でも安定したルートを構築するためのルーティング手法 を提案し、システムスループットの改善について評価を行った。提案手法は、
一定間隔でシステムの中継経路の更新を行い、その際、ノード間の伝搬損を過 去の履歴を加味した逐次平均で表すことで、漸近的に安定した中継経路へと収 束させることを特徴とする。提案手法を実機上で評価した結果、伝搬路が動的 に変動する実環境において安定した中継経路が構築でき、システムのスループ ットが改善されることが確認できた。
第二の研究は、IPT の効果を最大化する最適送信周期の自動設定プロトコルに ついてである。無線バックホールにおいて、IPT に基づいた多段無線中継を行う 場合、IPT 送信周期は最も重要なパラメータであり、適切に設定しないと IPT の 効果は発揮できない。IPT 送信周期は、ノード配置や周辺環境などに依存するた め、机上計算であらかじめ適切な数値を設定することは難しい。IPT 送信周期を 自動的に設定する手法が必要となる。本論文ではコアノードが各スレーブノー ドに対しトレーニングパケットを送信することにより、コアノードから各スレ ーブノードまでのスループットが最大になる IPT 送信周期を設定する手法を提
概要 iii
案し、実験とシミュレーション両方で評価を行った。その結果、提案手法によ って獲得された IPT 送信周期は常に最適な送信周期となることを確認した。
第三の研究は、指向性アンテナにより電波干渉を物理的に抑制した状態での IPT の実現についてである。指向性アンテナは送信電力を一定方向へ集中させる ことにより、他ノードへの干渉を軽減できる長所を有する。指向性アンテナの 適用により IPT の性能は更に向上するものと期待されるが、全方位接続性を担 保するためには異なる主軸方向の複数の指向性アンテナを装備する必要があり、
その適応的な切り替え処理で生じる遅延時間の影響によって中継伝送効率の低 下が生じる問題があった。本論文では各ノードに複数の無線インタフェースを 搭載し、インタフェース毎に固定的な指向性を持ったアンテナを接続すること に よ り 、 こ の 切 り 替 え 処 理 遅 延 の 影 響 を 軽 減 で き る 手 法 （ FDA: Fixed Directional Antenna）を提案した。FDA が適用された無線中継ノードに適した ルーティング手法を提案し、これと IPT を併用することによって高い中継伝送 効率を達成した。提案手法を実機テストベッドにより評価し、無指向性アンテ ナを適用した場合に比べて約 30％の性能改善が確認できた。
スマートフォンの爆発的普及に伴うトラフィックの急増により、無線通信の ブロードバンド化への要求は一層高まってきている。本論文の成果は、無線バ ックホールの多段無線中継時の性能を向上させるものであり、無線バックホー ルが適用できる建造物の対象範囲を広げるものである。これによってスモール セルの導入が促進され、大容量な無線通信網の実現を容易なものとする。
目次 iv
目次
第1
章 序章1 1.1
研究背景………1
1.2
無線バックホール………5
1.3
研究課題と目的………7
1.4
本論文の構成………10
第
2
章 無線バックホールを支える基本技術11 2.1
IEEE802.11 無線 LAN のアクセス制御方式………11
2.2
周期的間欠送信法(IPT)………16
2.3
本章のまとめ………19
第
3
章 無線バックホールにおける安定ルーティングプロトコル21 3.1
無線バックホールにおける従来のルーティング手法とその 問題点………21 3.2
ルーティング手法におけるアルゴリズムとメトリック……23
3.3
RSSI の逐次平均に基づく安定ルーティングプロトコル……32
3.4
提案プロトコルの実験による評価………37
3.5
本章のまとめ………55
第
4
章 無線バックホールにおける送信周期自動設定法56 4.1
既存の IPT 送信周期設定法………56
4.2
トレーニングによる送信周期自動設定法………58
4.3
提案手法の評価………61
4.4
本章のまとめ………69
目次 v
第
5
章 無線バックホールにおける指向性固定アンテナシステム71 5.1
指向性アンテナによる無線バックホールの性能強化………71 5.2
指向性アンテナの適用によって生じる諸問題と従来の対策…………
73 5.3
指向性固定アンテナシステム………75 5.4
FDA システムにおけるルーティング手法とパケット中継手法………
77 5.5
実験による評価………82 5.6
本章のまとめ………85
第
6
章 結論86
謝辞
89
参考文献
90
略語一覧 vi
略語一覧
ACK ACKnowledge
ADSL Asymmetric Digital Subscriber Line
CSMA/CA Carrier Sense Multiple Access with Collision Avoidance
CTP Clear To Send
CTPACK CTP ACKnowledge
CTS Clear To Send
CW Contention Window
CWmax Maximum CW
Cwmin Minimum CW
DCF Distributed Coordination Function
DIFS DCF IFS
ETX Expected Transmission Count FDA Fixed Directional Antenna FTTH Fiber To The Home
HSDPA High Speed Downlink Packet Access HSPA High Speed Packet Access
HSUPA High Speed Uplink Packet Access
IEEE Institute of Electrical and Electronic Engineers IETF Internet Engineering Task Force
IFS Inter Frame Space
IMT International Mobile Telecommunication IPT Intermittent Periodic Transmission
ITU-R International Telecommunication Union-Radio
略語一覧 vii
communication LAN Local Area network
LB Lunch Box
MAC Media Access Control MANET Mobile Ad-Hoc Network
MIMO Multiple Input Multiple Output NAV Network Allocation Vector
OPET Optimum Packet Scheduling for Each Traffic flow OSI Open System Interconnection
PCF Point Coordination Function
PIFS PCF IFS
PktPair Per-hop Packet Pair Delay
RSSI Received Signal Strength Indicator
RTS Request To Send
RTT Round Trip Time
SIFS Short IFS
SINR Signal to Interference plus Noise power Ratio
SOC System on Chip
SRL Short Retry Limit SSID Service Set Identifier
TM Training Metric
W-CDMA Wideband-Code Divided Multiple Access
WCETT Weighted Cumulative Expected Transmission Time Wi-Fi Wireless Fidelity
WMR Wireless Multi hop Relay
図目次 viii
図目次
1.1 4G への流れ……… 41.2 バックホールの種類……… 5
1.3 無線バックホール……… 6
2.1 IEEE802.11MAC の構成……… 12
2.2 Contention Window 長……… 13
2.3 Basic モードでのアクセス手順……… 13
2.4 隠れ端末問題（Hidden terminal problem） ……… 15
2.5 RTS/CTS モードでのアクセス手順……… 15
2.6 ノード配置……… 15
2.7 RTS/CTS モードにおけるリユースクラスタ 3 と無限大のホッ プ数に対するスループット……… 17 2.8 ３パケット時間長ごとにパケットを送信した場合に生ずる リユースクラスタ……… 19 3.1 重み付きグラフ G ……… 23
3.2 ツリー構造ネットワーク……… 31
3.3 最小伝搬損ルーティング……… 31
3.4 RSSI の時間変動……… 32
3.5 RSSI の逐次平均……… 32
3.6 コアノードの動作……… 36
3.7 スレーブノードの動作……… 36
3.8 PicoMesh LunchBox の外観……… 38
図目次 ix
3.9 実験フィールド 1：九州大学 W2 号館 8 階……… 38
3.10 実験フィールド 2：九州大学 W2 号館 2 階……… 38
3.11 実験フィールド１での伝搬路変動……… 40
3.12 実験フィールド 2 での伝搬路変動……… 40
3.13 実験フィールド 1 での受信レベル変動値分布……… 41
3.14 実験フィールド 2 での受信レベル変動値分布……… 41
3.15 固定ルートシステム１……… 42
3.16 固定ルートシステム 2……… 42
3.17 スループット測定系……… 42
3.18 固定ルートシステム１でスループットの変動……… 44
3.19 固定ルートシステム 2 でスループットの変動……… 44
3.20 実験シナリオ１のノード配置……… 44
3.21 実験シナリオ 2 のノード配置……… 44
3.22 Route 1 の中継ルート……… 47
3.23 Route 2 の中継ルート……… 48
3.24 パスの変動……… 48
4.1 衝突回避 IPT 周期設定法……… 57
4.2 メッシュクラスタ……… 57
4.3 シミュレーションシサイト１……… 62
4.4 マニュアルで測定したスループット値：Node 3, 4, 5, 6…… 62
4.5 マニュアルで測定したスループット値：Node 7, 10, 11……… 65 4.6 マニュアルで測定したスループット値：Node 14, 15, 16, 17 65 4.7 マニュアルで測定したスループット値：Node 18, 21, 22, 23 65 4.8 提案プロトコルにより計算された送信周期、⊿ = 100μsec、
Node 1 ～ 11………
66
4.9 提案プロトコルにより計算された送信周期⊿ = 100μsec、
Node 12 ～ 23………
66
4.10 提案プロトコルにより計算された送信周期, N = 300, ⊿ = 67
図目次 x
50, 100, 200μsec……… 4.11 システムスループットの改善……… 67
4.12 実験配置：九州大学ウェスト 2 号館 8 階……… 68
4.13 マニュアルで測定した IPT とスループット特性……… 68
5.1 中継経路間の電波干渉……… 72
5.2 指向性アンテナの適用による空間効率の向上……… 72
5.3 無指向性アンテナを搭載した３つのノード間の通信……… 74
5.4 指向性アンテナを搭載した３つのノード間の通信………… 74
5.5 Deafness（キャリアセンス不可）問題……… 74
5.6 F-3 指向性固定アンテナシステムのノード……… 76
5.7 ツリー構造の無線バックホール……… 79
5.8 コアノードのインタフェース毎に IPT を適用……… 79
5.9 PicoMesh SHELL の写真……… 84
5.10 実験シナリオのノード配置：九州大学 W2 号館 8 階……… 84
5.11 提案プロトコルにより構築されたルート……… 84
5.12 SHELL と LB のスループット特性……… 84
表目次 xi
表目次
3.1 LB の主要諸元……… 383.2 提案プロトコルのパラメータ……… 38
3.3 シナリオ 1 の実験結果……… 47
3.4 シナリオ 2 の実験結果……… 47
3.5 シナリオ 1: 従来手法実行時、各パスの出現頻度とスループ ット……… 51 3.6 シナリオ 1: 提案手法実行時、各パスの出現頻度とスループ ット……… 51 3.7 シナリオ 1: 平均スループットの比較と従来手法のスループ ット変動範囲……… 52 3.8 シナリオ 2: 従来手法実行時、各パスの出現頻度とスループ ット……… 52 3.9 シナリオ 2: 提案手法実行時、各パスの出現頻度とスループ ット……… 53 3.10 シナリオ 2: 平均スループット比較と変動範囲……… 54
4.1 シミュレーションパラメータ……… 63
4.2 マニュアル測定により得られた最適な送信周期（μsec）…… 66
4.3 N=300 の場合のプロトコルの実行時間……… 67
4.4 プロトコルにより計算された送信周期……… 68
第1章 序章 1
第1章 序章
本章では、本論文における研究の背景と目的、及び論文の構成について説明 する。
1.1
研究背景情報化社会の発展に伴いインターネットは我々の生活に深く浸透し、今や日 常 生 活 に な く て は な ら な い 存 在 と な っ た 。 ADSL （ Asymmetrical Digital Subscriber Line）や FTTH（Fiber To The Home）などの有線ブロードバンド通 信の普及は、ありとあらゆる情報を、インターネットを経由して高速に送受す ることを可能にした。この流れは、無線通信の世界へと波及しつつあり、その 牽引役はスマートフォンやタブレットＰＣである。特に 2007 年に出現した iPhone を契機とし、スマートフォンの普及速度は一気に高まり、市販されてい る携帯端末の過半数が同種端末となるまでに市場は変化した。これらのスマー トフォンのデータ通信量は従来のフィーチャーフォンのデータ通信量に比べて 数十倍であるとされ、携帯通信網へ大きな負荷をかけている。無線通信システ ムの大容量化は喫緊に取り組むべき課題として、昨今の無線通信キャリアの最 大の関心事である。本節ではこれまでの無線通信システムの進化について概観 し、無線通信の大容量化への取り組みについて説明する。
無線通信システムの代表例として携帯電話システムを取り上げ、説明を行う。
日本の携帯電話サービスは 1979 年にアナログ方式を用いた音声通話を中心とす る第一世代が開始されて以来、1993 年にはデジタル方式を採用した第二世代方 式、2001 年にはデータ通信機能を強化した第三世代方式が開始された。現在日 本の携帯電話サービスの加入者数は一億人を超え、そのほとんどが第三世代方 式である。更に第四世代方式に向け、2010 年から LTE（Long Term Evolution）
第1章 序章 2
のサービスも部分的に開始されている。
第一世代の携帯電話システムはアナログ方式を採用していて、各利用者に異 な る無 線周波数 を割 り当 て る周波 数 分割 多重 （ FDMA：Frequency Division Multiple Access）によりチャネルを割り当てている。当方式は周波数利用効率 が悪く、システムの容量に限界があった。そのため第二世代システムではデジ タル通信方式が採用され、その代表例である GSM システムでは一つの周波数チ ャネルを時間で分割した、時間分割多重（TDMA：Time Division Multiple Access）
によりチャネル割り当てが行われた。GSM を進化させた EDGE（Enhanced Data Services for GSM Evolution）ではデータ伝送レートが最大 384Kbps まで達成 できる。第二世代から第三世代へと至る過渡期には、符号分割多重（CDMA：Code Division Multiple Access）方式の研究開発が活発化した。CDMA 方式では隣接 した基地局間で同一周波数を割り当て、さらに一つの端末が複数の基地局と通 信を行うことでシステム容量の拡大を図った。第三世代方式は標準化機構 ITU-R
（International Telecommunication Union-Radio Communication）において国 際標準化が進められた。ITU-R は、第三世代方式が満たすべき要件として IMT-2000(International Mobile Telecommunication 2000）を勧告した。同勧 告では、国際ローミングへの対応や最大２Ｍｂｐｓのブロードバンドデータ通 信が盛り込まれた。ITU-R の勧告後、第三世代方式の標準化の推進母体として、
1998 年に各国の標準化団体等が連携し、3GPP（Third Generation Partnership Project）が設立された。3GPP が仕様を策定した第三世代方式の代表的方式であ る WCDMA（Wideband Code Division Multiple Access）システムでは、静止時の 最大下り伝送レートとして 2Mbps をサポートした。但し光ファイバーなどの有 線ブロードバンド回線で提供されている 100Mbps オーダーの伝送レートに比べ れば依然ナローバンドであった。
有線ブロードバンド環境において発達してきた高度なサービスをモバイル環 境でも使用するためには、無線通信の更なるブロードバンド化が必須である。
以下では 4G 或いは Beyond 3G とも呼ばれる、次世代ブロードバンド無線通信方 式への流れについて説明する。ITU-R では 2003 年６月に“Framework and overall objectives of the future development of IMT-2000 and systems beyond
第1章 序章 3
IMT-2000”というタイトルの「ITU-R M.1645」勧告を発表した。本勧告では、
次世代のブロードバンド通信インフラは、そのコア・ネットワークはすべて IP 化し、低速移動時 1Gbps および高速移動時 100Mbps を実現するシステムである ことが規定されている。本勧告を想定して、各国で次世代ブロードバンド無線 通信へ向け開発が進められた。2006 年には W-CDMA の拡張モードとして、HSDPA
（High Speed Downlink Packet Access）の運用が開始された。HSDPA は下り方 向の伝送レートを最大 14.4Mbps まで向上させた仕様となっている。その後、上 り方向の高速化が行われ（HSUPA: High Speed Uplink Packet Access）、HSDPA とともに総称して HSPA（High Speed Packet Access）と呼ばれている。HSPA は 既存３G ネットワークとの互換性を重要視していることから、第 3.5 世代方式と も呼ばれている。
一方、3GPP では HSPA と並行して新しい無線アクセス方式である、LTE（Long Term Evolution）、さらにその先の LTE Advanced の標準化も進められた。LTE で は既存の 3G ネットワークとの互換性に囚われることなく、OFDM（Orthogonal Frequency Division Multiplexing）や MIMO（Multiple-Input Multiple-Output）
などの新しい技術の導入により高速データ伝送を図っている。OFDM は低速レー トの情報信号を被変調波とする複数のサブキャリア変調波を束ねることを特徴 としており、周波数選択性フェージングに対する耐性が強く、高速データ伝送 を可能としている。一方、MIMO は、送信機と受信機においてそれぞれ複数のア ンテナを使用することで、異なる情報信号を空間的に多重し、同一時間同一周 波数を用いて信号を伝送するため、安定した通信を実現可能としている。LTE は 下り方向で最大 100Mbps、上り方向で最大 50Mbps を、そして LTE-Advanced は下 り方向最大 1Gbps、上り方向最大 500Mbps の伝送レートを目標としている。
ブロードバンド無線通信を実現するためのその他のアプローチに、無線 LAN
（Local Area Network）と WiMAX（Worldwide Interoperability for Microwave Access）による取り組みがある。無線 LAN システムは 90 年代前半に出現してか ら、家庭やオフィスのブロードバンド無線インフラとして急速に普及した。無 線 LAN は標準化団体 IEEE（Institute of Electrical and Electronic Engineers）
802 委員会により発行された 802.11 標準規格に準拠しており、無線 LAN 業界の
第1章 序章 4
図 1.1 4G への流れ
団体である WiFi（Wireless Fidelity） Alliance により装置の相互接続のため の認証が行われる。無線 LAN の最大伝送速度は 802.11b（1997 年）では 11Mbps、
802.11a と（1999 年）802.11g（2003 年） では OFDM 変調方式を採用し 54Mbps まで上げられた。更に 2010 年に仕様が確定した 802.11n では最大 600Mbps まで の高速通信をサポートしている。1999 年スタートした IEEE802.16 ワーキング・
グループでは MAN（Metropolitan Area Network、都市域通信網）の標準を策定 し、その後 2001 年４月 WiMAX フォーラムが形成された。IEEE802.16 は当初、ポ イントツーポイントあるいはマルチポイントツーマルチポイント型の固定無線 通信のための規格であったが、新たに移動端末への接続性を保証するべく、
IEEE802.16 を発展させた IEEE802.16e が策定された。WiMAX として現在サービ スが展開されている通信方式は、一般にこの IEEE802.16e 規格を指す場合が多 い。同規格の最大伝送速度は 20MHz 帯域幅の時約 75Mbps に達する。
図 1.1 に 4G への大まかな流れを示している。上記で説明したように、4G へ向 け無線通信の伝送速度は著しく向上しているものの、スマートフォンの普及に より急増しているトラフィックに追いつくことは、LTE の導入をもっても困難と 言われている。無線通信システムには、データ伝送レートの向上だけではなく、
トラフィックをさばく能力、即ちシステム容量の拡大も欠かせない。KDDI の発
第1章 序章 5
図 1.2 バックホールの種類
表によれば 2011 年の時点で、スマートフォンはまだ 10％しかないが、既にトラ フィックの 60％を超えていて、2012 年に LTE を導入した後もシステム容量を超 えるトラフィックが発生すると予測されている。急増するトラフィックの対応 策には、データ通信を様々な回線に分散させる「データオフロード」、例えば WiFi 或いは WiMAX の回線にトラフィックを分散させる取り組み、或いは LTE により スモールセルを採用するなどの手法がある。
1.2 無線バックホール
本節では無線通信システムの高速化と大容量化に伴い顕在化する基地局敷設 コスト増大の問題について説明し、その対策である無線バックホールについて 説明する。
無線通信システムでデータ伝送の高速化を行うためには、ビット当たりの送 信電力を大きくする必要があり、送信電力の制限下で要求された伝送レートに 達するためには、基地局と端末間の通信距離を短縮し、各基地局の守備するエ リアを狭小化することが必要となる。一方無線通信システムの大容量化を行う ためには、各基地局の守備範囲を縮小することにより、基地局当たりの負荷を 軽減することが必要となる。そのためスモールセル（半径数十メートルの狭小 基地局）化は次世代無線通信システムにおいて必要かつ必須なことである。但 し広いサービスエリアをカバーするためには、スモール基地局を多数敷設する 必要が生じ、基地局の敷設コストが増える。そのためコスト削減は次世代無線 通信を実現する鍵と言っても過言でない。
第1章 序章 6
図 1.3 無線バックホール: 基地局間の回線及びコアノードと基幹網を結ぶ回線
基地局敷設コストを削減する手法として、各基地局を無線で多段中継するセル ラシステムが検討されている。基地局群のうち幾つか（コアノード）を有線で 基幹網へと接続し、その他（スレーブノード）はコアノードを介した多段無線 中継により基幹網と接続される。当該無線中継網は通称、無線バックホールと 呼ばれている。ここでバックホールとは基地局と基幹網を接続する回線のこと を指し、基幹網とは遠隔地を結ぶ広域ブロードバンド通信網を指す。バックホ ールは通信媒体の採用により有線バックホールと無線バックホールに分類でき、
無線バックホールはさらにメッシュ型とツリー型、そして統計メッシュ型など に分類できる（図 1.2）。メッシュ型の無線バックホールは、ノード間を互いに Multi-Point to Multi-Point 状に接続し、中継経路を網の目状に形成している ため、無線メッシュネットワークとも呼ばれている。無線メッシュネットワー クでは、各ノードが複数の中継パスを有するため、パケットの伝送調停が必要 となり、中継伝送効率が低下する問題がある。これに対し、ツリー型の無線バ ックホールでは有線網にケーブルで接続されたノードを基幹とし、各ノードに おける枝分かれ分岐点の数を減らすことが可能であるため、パケットの衝突調 停にかかる制御負荷を軽減し、パケット伝送効率を向上することが可能となる。
そのため本論文ではツリー構造の無線バックホールを検討の対象とする。一方 ツリー型無線バックホールにおいて、伝搬路の時間変動を考慮し、システムの 中継経路を定期的に更新すると、長期間で観測した平均的ルートはメッシュ状 になる。このような経路制御手法を採用した無線バックホールは統計メッシュ
第1章 序章 7
型と呼ばれている。図 1.3 にツリー型の無線バックホールおける基幹網、アク セス網の関係を模式的に示している。ここでアクセス網とは移動端末と基地局 の間のアクセス回線のことを指す。
無線バックホールはこれまで広く応用されている。例えば北米ではデジタル デバイド解消のため地方自治体が中心となったブロードバンド無線インフラを 敷設する動きが活発になり、そこで低コストで基地局を整備するために無線バ ックホールが利用されている。一方 IEEE802.11s では無線 LAN を用いた無線マ ルチホップ中継に関する標準化が行われている。無線バックホールでは基地局 と基幹網を接続するための有線回線の敷設数を削減できるため、システム全体 の敷設コストを低減することができる。また基地局が有線で縛られないため、
基地局の再配置や追加が楽に行える利点も有する。無線中継可能な段数が多け れば多いほど、システムの敷設に必要な有線回線の敷設量を削減できる。また 欧州などで数多く現存する歴史的建造物等の一部の建物における無線エリア構 築では、有線回線の敷設が不可能な場合があり、無線中継可能な段数が多けれ ば多いほど、当該無線システムの適用可能範囲を拡大することができる。すな わち許容可能な無線中継段数は、無線バックホールの性能を測るもっとも重要 な指標である。
1.3
研究課題と目的本論文では無線バックホールにおける高性能多段無線中継手法について検討 を行う。無線バックホールの性能を改善するアプローチとして、主に２つの手 法が考えられる。その一つは与えられた無線インタフェース（OSI 参照モデルが 指すところの第１層及び第２層部分、即ち MAC 層以上）に変更を加えることな く、多段中継することにより中継伝送効率を最大化するシステムレベルでの対 応である。もう一つの手法は新しい無線インタフェースの設計による、リンク レベルでの対応である。リンクレベルでの対応は LSI の設計などを必要とする ためコストの増加が大きく、安価で無線バックホールを構築することは難しい。
そのため本論文では前者のシステムレベルによる無線バックホールの性能改善 に着目する。
第1章 序章 8
多段無線中継を阻害する最大の課題は電波干渉である。著者が所属している 研究室では無線バックホールおいて多段無線中継を高効率に行う手法として、
周期的間欠送信法（IPT：Intermittent Periodic Transmission、[24]）を提案 している。IPT は、パケットの送信源となるノードにおいて一定の送信周期（IPT 送信周期）を持って間欠的に送信することにより、中継経路上での同一周波数 リユース間隔を調整し、最適な送信周期を設定することで電波干渉によるパケ ット衝突を回避することを特徴とする。IPT による中継伝送効率の改善効果は実 証実験によっても確認されており、10 段以上の多段中継も可能であることが実 機上で示されている。本研究室では IPT を基本中継方式とし、設置すれば即座 にブロードバンド通信エリアが確保できるような、小型で可搬性のある無線バ ックホールの研究開発を進めている。その推進母体として、MIMO-MESH プロジェ クトを立ち上げた。MIMO-MESH プロジェクトは「地域イノベーションクラスター プログラムグローバル型（第 II 期）」事業のプロジェクトで、文部科学省と福 岡県の補助を受けている（2007-2012,[37])。著者は本プロジェクトにおいて、
ルーティングとパケット中継プロトコルの研究開発に従事している。
文献[24]では IPT による性能改善は示しているものの、IPT 送信周期の具体的 な設定手法については検討しておらず、無線バックホールのルーティング手法 が IPT の性能へ及ぼす影響についても検討していない。さらに指向性アンテナ が適用された無線バックホールでの IPT の応用方法についても検討されていな い。そのため本論文では IPT によりもたらされた多段無線中継の性能を更に向 上させるために、以下に示す３つの研究について取り組んだ。
第一の研究は、安定した IPT の運用を保証するための中継経路の安定性改善 である。IPT はツリー構造の中継経路上で運用され、中継経路の設定（ルーティ ング）は IPT の伝送性能を大きく左右する。無線バックホールシステムでは各 基地局は固定的に設置されるため、基地局間の伝搬路特性は変動しないものと 誤解される場合があるが、実際には人の移動やドアの開閉等によって変動する。
従来のルーティング手法では、無線伝搬路特性の時間変動を考慮しておらず、
経路を構築した瞬間の伝搬路特性によって構築された中継経路は、それ以降も 最適である保証はない。動的な伝搬路特性の変動に追随しようと、ルーティン
第1章 序章 9
グを繰り返すと、中継経路が不安定となってしまう[31]。本研究を始める際に、
無線バックホールにおいて安定的な中継経路を構築するルーティング手法はま だ提案されていなかった。従来のルーティング手法とその問題点については第 3 章で詳しく検討する。本論文では無線伝搬路特性が時間変動する環境でも安定 したルートを構築するためのルーティング手法を提案し、システムスループッ トの改善について評価を行った。提案手法は、一定間隔でシステムの中継経路 の更新を行い、その際、ノード間の伝搬損を過去の履歴を加味した逐次平均で 表すことで、漸近的に安定した中継経路へと収束させることを特徴とする。提 案手法を実機上に実装し、ルーティング特性とスループットに改善について評 価を行う。
第二の研究は、IPT の効果を最大化する最適送信周期の自動設定プロトコルに ついてである。無線バックホールにおいて、IPT に基づいた多段無線中継を行う 場合、IPT 送信周期は最も重要なパラメータであり、適切に設定しないと IPT の 効果は発揮できない。IPT 送信周期は、ノード配置や周辺環境などに依存するた め、机上計算であらかじめ適切な数値を設定することは難しい。IPT 送信周期を 自動的に設定する手法が必要となる。本研究を始める際パケットの衝突回避を 可能にする IPT 送信周期設定法が提案されていた[23]。但し本手法は既存 MAC プロトコルの変更を必要としているため、実用性に乏しい。本論文ではコアノ ードが各スレーブノードに対しトレーニングパケットを送信することにより、
コアノードから各スレーブノードまでのスループットが最大になる IPT 送信周 期を設定する手法を提案し、実験とシミュレーション両方で評価を行う。
第三の研究は、指向性アンテナにより電波干渉を物理的に抑制した状態での IPT の実現についてである。指向性アンテナは送信電力を一定方向へ集中させる ことにより、他ノードへの干渉を軽減できる長所を有する。指向性アンテナの 適用により IPT の性能は更に向上するものと期待されるが、全方位接続性を担 保するためには異なる主軸方向の複数の指向性アンテナを装備する必要があり、
その適応的な切り替え処理で生じる遅延時間の影響によって中継伝送効率の低 下が生じる問題があった[30]。本論文では各ノードに複数の無線インタフェー スを搭載し、インタフェース毎に固定的な指向性を持ったアンテナを接続する
第1章 序章 10
ことにより、この切り替え処理遅延の影響を軽減できる手法（ FDA: Fixed Directional Antenna）を提案した。FDA が適用された無線中継ノードに適した ルーティング手法を提案し、これと IPT を併用することによって高い中継伝送 効率を達成した。提案手法を実機テストベッドにより評価し、無指向性アンテ ナを適用した場合との比較を行う。
1.4
本論文の構成本論文の構成は以下の通りである。
第２章では本論文の背景となる無線 LAN 規格と、本論文で研究の基礎として いる IPT の概念など、無線バックホールを支える基本技術について説明する。
第３章では本論文の最初の研究課題である、無線バックホールにおいて安定 した中継経路を構築する手法について検討を行う。本章ではまず無線バックホ ールにおける従来のルーティング手法の問題点について指摘し、次に伝搬路の 時間変動を考慮した安定ルーティング手法を提案する。提案手法を実機テスト ベッド実装し、実験により評価を行い、更に提案手法によるスループットの改 善に対して評価を行う。
第４章では本論文の二番目の研究課題である、無線バックホールにおける送 信周期自動設定法について検討する。本章ではまず既存の送信周期自動設定法 とその問題点について説明し、次にトレーニングに基づいた新しい送信周期自 動設定手法を提案する。そして提案手法を実験とシミュレーション両方で評価 を行う。
第５章では本論文の三番目の課題である無線バックホールにおける指向性ア ンテナの適用方法について検討する。本章ではまず無線バックホールにおいて 指向性アンテナを適用する場合に生じる問題について説明し、次にその対策と して指向性固定アンテナシステム(FDA)について提案する。次に FDA が適用され た無線中継ノードに適したルーティング手法を提案し、FDA と IPT を併用する手 法について提案する。そして提案手法を実機テストベッドにより評価する。
最後に第６章で本論文の結論を述べる。
第2章 無線バックホールを支える基本技術 11
第2章
無線バックホールを支える基本技術
本論文では低コストでの無線バックホールの構築を可能とするために、無線イ ンタフェースに市場で購入できる汎用の無線モジュールを使用することを前提 とする。特に近年急速に普及され高性能且つ安価になっている IEEE802.11 無線 LAN モジュールを採用することにした。そのため本章ではまず無線 LAN 規格に関 する基本概念について説明し、次に本論文で基礎としている周期的間欠送信法 について説明する。
2.1
IEEE802.11 無線 LAN のアクセス制御方式本節では IEEE802.11 無線 LAN([41])でのアクセス制御機構の詳細を説明する。
IEEE802.11MAC (Media Access Control)ではアクセス制御機能として CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)が採用されてい る。CSMA/CA では、パケットの送信を試みようとする無線局が無線チャネルの使 用状況をキャリアセンスによる搬送波の検出有無により判断し、搬送波を検出 する間（Busy）は送信待機し、一定期間検出しなければ（Idle）送信を開始す る、図 2.1 には IEEE802.11MAC の構成を示している。IEEE802.11MAC におけるア クセス制御方式には DCF (Distributed Coordination Function)と PCF (Point Coordination Function)の 2 つが規定されている．基本アクセス制御方式とさ れている DCF では各無線局が CSMA/CA により自律分散的にパケットの送信タイ ミングを決定する。しかし CSMA/CA では偶然同時にパケットを送信し、パケッ ト衝突となり通信が失敗してしまう可能性があるため、IEEE802.11MAC ではオプ ションとして PCF を設けている。PCF では無線セル内においてポーリングに基づ く集中制御によるアクセス制御が行われる、ポーリングとは、基地局が各端末 に順番にポーリング信号を送信し、基地局からポーリング信号を受け取った端 末のみがパケットの送信を許可されるというアクセス手順である。基地局が PCF
第2章 無線バックホールを支える基本技術 12
図 2.1 IEEE802.11MAC の構成
をサポートする場合、無線セル内では DCF によるアクセス制御を行う期間と、
PCF によるアクセス制御を行う期間を周期的に切り替えて運用する。本研究では 複数の基地局が集中管理されなくとも高い中継伝送効率を達成可能な中継基地 局自律分散的型のマルチホップ中継を目指しているため、DCF による運用を前提 とする。
IEEE802.11 無線 LAN の基本アクセス制御方式である DCF では、CSMA/CA とラ ンダムバックオフ（Random Backoff）により、同一周波数を利用する複数無線 局の自律的にアクセス制御できるようにする。ランダムバックオフはチャネル が Idle となった直後に複数の無線局が同時に送信を開始することを避けるため に設けられている。バックオフ期間では、Slot time で規定される時間長の整数 倍の時間送信待機し、このときの整数は[0, CW (Contention Window)長]の範囲 で一様乱数により決定される。図 2.2 に示すように CW 長は新規のデータパケッ トを送信する度に規定された最小値（Minimum CW, MinCW）に設定され、再送の 都度指数的に増加するが、規定された最大値（Maximum CW, MaxCW）に到達する とそれ以上の増加は行わない。また、IEEE802.11 では信号を送信する前の時間 間隔として IFS (Inter Frame Space)を定めている。IFS には SIFS (Short IFS)，
PIFS (PCF IFS)、および DIFS (DCF IFS)があり、その大きさ（SIFS < PIFS < DIFS）
によりパケットの種類に応じた送信優先度を与える。
Distributed Coodination Function
(DCF) Point
Coodination Function
(PCF) MAC
Extent
Used for Contention Services and basis for PCF Required for Contention-
Free Services
第2章 無線バックホールを支える基本技術 13
図 2.2 Contention Window 長
図 2.3 Basic モードでのアクセス手順
DCF にはさらに大きく 2 つのアクセス手順、Basic モードと RTS/CTS モードが 規定されており、以下では Basic モードと RTS/CTS モードのそれぞれについて 説明する。
15 31 63 127
255 511
1023 1023
Initial AttemptFirst RetransmissionSecond RetransmissionThird Retransmission MinCW
MaxCW
Source
Destination
Other
DIFS
DIFS
Data
SIFS
ACK Slot time
Backoff-Window
Busy Medium DIFS
Data Defer Access Backoff After Defer Backoff period
第2章 無線バックホールを支える基本技術 14
2.1.1 Basic モード
DCF において、Basic モードの基本アクセス手順を図 2.3 に示す。
図 2.3 に示すように、パケットの送信を試みようとする無線局（Source，Other）
はキャリアセンスによりチャネルが Idle である期間が DIFS 期間続くとバック オフ期間に入る。さらにチャネルが Idle である期間がバックオフ期間続くとデ ータパケットの送信を開始する。バックオフ期間中に搬送波を検出すると、残 りのバックオフ期間を保持し、チャネルが DIFS 期間 Idle になるのを待つ。チ ャネルが再び DIFS 期間 Idle になると、続きのバックオフを再開する。目的局
（Destination）では、データパケットの受信に成功すると、SIFS 期間を経て、
確認応答である ACK（Acknowledge）パケットを送信局（Source）に送信する。
送信局はデータパケットの送信後、規定時間内に ACK を受信しなければ通信に 失敗したと判断し、再送を行うためにキャリアセンスを開始する。送信局では 再送においても同様の手順を繰り返すが、前述のように CW 長は MaxCW に達する までは再送の都度指数的に増加する。
2.1.2RTS/CTS モード
Basic モードでは回避できないパケット衝突の例を図 2.4 に示す。図 2.4 では ノード A がノード B に向けてパケットの送信を行い、ノード C もノード B に向 けて送信を試みている。ここでノード A とノード C が距離的に離れた位置関係、
あるいは間に障害物が存在するなどの理由で互いに搬送波を検出できない場合、
ノード A がパケットを送信中にも関わらずノード C はノード B に向けパケット の送信を開始してしまい、パケット衝突となり通信が失敗する。このように、
複数の無線局が互いに搬送波を検出できない場合、同時にパケットを送信し互 いに干渉を与え通信が失敗してしまう問題を、隠れ端末問題と呼ぶ。
IEEE802.11 では隠れ端末問題のような CSMA/CA が有効に機能しない伝搬環境 に対応するために RTS (Request To Send) / CTS (Clear To Send)と呼ばれる対 策が定義されている。RTS/CTS モードの通信では、Basic モードの手順に加え、
データパケットの送信の前に送信局‐目的局間で RTS パケットならびに CTS パ ケットのやり取りを行う。RTS/CTS モードでのアクセス手順の例を図 2.5 に示す。
第2章 無線バックホールを支える基本技術 15
図 2.4 隠れ端末問題（Hidden terminal problem）
図 2.5 RTS/CTS モードでのアクセス手順
図 2.6 ノード配置
送信局（Source）では、Basic モードの手順と同様にキャリアセンスによりチャ ネルが DIFS 期間 Idled であるとバックオフを開始する。送信局はバックオフ期
A B C
Currently Transmitting
Wants to Transmit to B Carrier Sense
Range of A
Carrier Sense Range of C
Source
Destination
Other
DIFS
DIFS
Data
SIFS
ACK Slot time
DIFS
Defer Access
Backoff After Defer RTS
CTS SIFS SIFS Backoff
NAV (RTS) NAV (CTS)
始点ノード 終点ノード
第2章 無線バックホールを支える基本技術 16
間が終了すると、データパケットではなく RTS パケットを送信する。RTS パケッ トには送信局がこれからチャネルを使用する期間の情報が含まれている。目的 局（Destination）は RTS を受信後すぐに CTS パケットを送信局に向け送信する。
CTS パケットにも RTS の情報を基にこれからチャネルが使用される期間の情報が 含まれている。RTS、CTS パケットは送信局ならびに目的局周辺の無線局でも受 信され、受信した無線局では NAV (Network Allocation Vector)が設定され、チ ャネルの予定使用期間の間送信待機状態となる。こうして送信局は隠れ端末の 関係にある無線局にもチャネルの使用を報知できるため、隠れ端末に起因する データパケットの衝突が回避できる。無線局はバックオフ期間中に RTS/CTS パ ケットをすると、残りのバックオフ期間を保持し、NAV の期間経過した後チャネ ルが DIFS 期間 Idle になるのを待って、続きのバックオフを再開する。RTS/CTS モードにおいても、RTS パケットもしくは CTS パケットの伝送時には隠れ端末の 影響を受けるが、しかし、両パケットともデータパケットに比べて時間長が短 く、隠れ端末による RTS/CTS パケットの衝突確率は低い。
2.2
周期的間欠送信法（IPT）本節では、前節で解説した IEEE802.11 規格の無線 LAN を適用した無線バック ホールの特性を示し、周期的間欠送信法（IPT）の原理について詳述する。
2.2.1無線 LAN を使用した無線バックホールの特性
IEEE802.11 規格の無線 LAN を無線中継回線インタフェースに用いた場合の無 線バックホールにおいて周波数リユース効果がどの程度発揮されるかを計算機 シミュレーションにより調べる。想定したノード配置を図 2.6 に示す。図のよ うにノードを直線上に等間隔で配置し、パケットの送信源を始点ノード、最終 到着ノードを終点ノードとする。ここではノードを 15 個並べ、常に隣のノード に中継する 14 ホップの中継伝送を行う場合を考える。各ノードは中継するべき パケットを受信すると直ちに中継する。自ノードと、自ノードから互いに干渉 せずに同時にパケット送信ができる最も近いノードとの間
第2章 無線バックホールを支える基本技術 17
図 2.7 RTS/CTS モードにおけるリユースクラスタ 3 と 無限大のホップ数に対するスループット
に含まれるノード数に１を加えた値をリユースクラスタと定義する。例えば、
あるノードが他のノードへ及ぼす干渉が隣接する 1 ノード先までで、2 ノード以 上先のノードでの干渉は 0 だとすると、リユースクラスタは 3 となる。所要 SINR は 10dB とし、受信したパケットの品質が当該所要値以上の場合は確率 1 で受信 に成功し、そうでない場合は確率 1 で受信に失敗するものとする。データパケ ット長は 11Mbps 伝送で 1500 バイト相当のデータパケットを送信する場合を想 定して、130SIFS とする。また ACK、RTS、CTS パケットのパケット長は同一とし、
データパケットの 1/6.5 倍とした。最小 CW 長は 64[SIFS]とし、最大 CW 長は 2048[SIFS]とした。
評価は終点ノードで観測される実効スループットにより評価する。実行スル ープットは次のように定義する。まず終点ノードにおいて先頭データパケット の受信開始から最終データパケットの受信完了までの時間を測定し、終点ノー ドにおいて受信した全データパケットに含まれる情報ビット数を当該時間で割
第2章 無線バックホールを支える基本技術 18
ったものをスループットとする。次に終点ノードにおいて連続するデータパケ ットが空き時間なくかつ重複なく受信できるとした場合のスループットを最大 スループットとする。また終点ノードにおいて同一パケットの平均受信回数を パケット重複率とし、スループットを最大スループットならびに重複率で割っ たものを実効スループットとする。リユースクラスタ 3 の場合と無限大の場合 に RTS/CTS モードを用いた場合のホップ数に対するスループットの評価結果を 図 2.7 に示す。
図 2.7 から分かるように、リユースクラスタ無限大では隠れ端末が発生しな いため、ホップ数が尐ない領域においてリユースクラスタ 3 の場合よりもわず かに高いスループットを示している。しかし、ホップ数が大きくなるにつれて リユースクラスタ 3 の方が無限大の場合よりも相対的にスループットは高くな る。すなわち、ホップ数が大きな領域では、隠れ端末の発生する危険性が高ま っても周波数リユースの効率を高めるほうが、より中継伝送効率を高められる のである。これを周波数リユース効果と呼ぶことにする。このようなマルチホ ップネットワークにおける周波数リユース効果はフィールド実験でも確認され ている（[11]）。更なる周波数リユース効率の改善を達成するために、周期的間 欠送信法が提案された（[20]）。
2.2.2周期的間欠送信法(IPT)
周期的間欠送信法（IPT）では、パケット送信源となるノードにおいて連続的 にパケットを送るのではなくある時間間隔を付与する。この方法により時間間 隔に応じて中継経路上の同一周波数リユース間隔を意図的に調整することが可 能となり、適切な時間間隔を設定することによりスループットの改善が達成さ れる。
IPT の原理を詳細に説明する。11 個のノードを直線上に配置し常に隣のノー ドへ中継する 10 ホップの中継伝送を行う場合を考える（図 2.8）。説明の利便 性を考え、パケットの発信源となるノードを始点ノード、最終到着ノードを終 点ノードと定義する。パケット長は常に一定であるものとする。今、始点ノー ドから 3 パケット時間長おきにパケットを送信する場合を考える。
第2章 無線バックホールを支える基本技術 19
図 2.8 ３パケット時間長ごとにパケットを送信した 場合に生ずるリユースクラスタ
図 2.8 のように、始点ノードより 3 パケット時間長毎にパケットを送信した 場合、同時にパケットの送信が行われるノードの間隔は 3 である。各受信ノー ドにおいてパケットが正しく受信できるならば、これはすなわちリユースクラ スタ 3 の同一周波数繰り返しが生じることを意味する。この場合始点ノードに おいて観測されるスループットは 1/3（最大スループットに対する相対値）とな る。このように送信源ノードにおいて連続的にパケットを送信するのではなく ある送信時間間隔によりパケットを送信することによりリユース間隔を制御す ることができる。適当なパケット送信時間間隔の設定を行えば規則的な周波数 リユースが行われ、これにより中継ノード間のパケット衝突が軽減されてスル ープットを向上させることができる。
2.3
本章のまとめ本章では IEEE802.11 準拠の無線 LAN の概要について説明し、IPT の基本原理 について説明した。
本 論 文 で は 低 コ ス ト で 無 線 バ ッ ク ホ ー ル が 構 築 で き る よ う に 、 市 販 の
第2章 無線バックホールを支える基本技術 20
IEEE802.11 準拠の無線 LAN を無線インタフェースに使用している。そのため無 線 LAN を使用した無線バックホールにおけるパケット伝送特性について評価を 行い、周波数リユースによる性能改善の可能性について説明した。その後無線 バックホールにおいて意図的に周波数リユースを形成することにより中継効率 を改善する IPT の基本原理について説明した。
IPT は無線バックホールにおいてパケット中継の性能向上を実現するための 鍵である。本論文のこの以降の各章では、IPT を適用した際の無線バックホール の性能を更に向上するための手法について検討を行う。
第3章 無線バックホールにおける安定ルーティング手法 21
第3章
無 線 バ ッ ク ホ ー ル に お け る 安 定 ルーティング手法
本章では無線バックホールにおいて安定的に IPT を運用するために、安定し た中継経路を構築する手法について検討を行う。
無線バックホールにおける中継経路の設定（ルーティング）は IPT の性能を 大きく左右する。無線バックホールにおいて IPT を応用してシステムの性能改 善を図る時、コアノードはスレーブノード毎に適切な送信周期を持ってパケッ ト送信を行う。但しその際パケットの中継経路はすでに確定されていることと している。そのため中継経路を適切に設定することは IPT の性能を発揮するた めの重要な条件である。
無線バックホールシステムでは各基地局は固定的に設置されるため、基地局 間の伝搬路は変動しないと誤解される場合があるが、実際には人の移動やドア の開閉等によって基地局間の伝搬特性が変動する。従来のルーティング手法で は、無線伝搬路特性の時間変動を考慮しておらず、経路構築の瞬間の伝搬路特 性だけによって経路を構築しているが、構築された中継経路はそれ以降も最適 である保証はない。動的な伝搬路特性の変動に追随しようと、ルーティングを 繰り返すと、中継経路が不安定となってしまう。
本章ではまず無線バックホールにおける従来のルーティング手法とその問題 点について説明し、次に無線伝搬路特性が時間変動する環境でも安定した中継 経路を構築する新しいルーティング手法を提案し、評価を行う。
3.1
無線バックホールにおける従来のルーティング手法とその問題点本節ではまず無線バックホールにおける既存のルーティング手法の概要につ いて説明し、次にその問題点について指摘する。
第3章 無線バックホールにおける安定ルーティング手法 22
無線バックホールは従来 Ad-Hoc ネットワークの分野で研究されていて、既に 多 数 の ル ー テ ィ ン グ 手 法 提 案 さ れ て い る 。 標 準 化 機 構 IETF （ Internet Engineering Task Force）の MANET（Mobile Ad-Hoc Networks）WG では Ad-Hoc 型の無線マルチホップネットワークのためのルーティング手法の標準化も進め ている。従来のルーティング手法は On-Demand 型と Static 型に分類できる。
On-Demand 型のルーティング手法では通信要求が発生する都度ルーティング処 理が行われ、通信が終了すると当該ルートは削除される。On-Demand 型のルーテ ィング手法はルーティング処理の負荷は大きいがネットワークトポロジーの変 化に早く対応でき、移動性の大きいモバイルアドホック型ネットワークに向い ている。Static 型ルーティング手法ではネットワークを構築する際、システム の起動と同時にルートを構築し、その後は当該ルートを保持したままサービス を提供する。本論文で検討している無線バックホールで、各基地局は固定して 設置されるため Static 型のルーティング手法が適している。そのため本論文で は Static 型のルーティング手法に焦点を絞る。
無線バックホールで各基地局は固定設置されるが、伝搬路は人の動きなどに よるフェージングの影響を受け変動する。しかし、従来のルーティング手法で は伝搬路の変動を考慮したアルゴリズムの設計がなされていない。例えば、文 献[31], [13], [5], [25], [3], [12]では伝搬路の時間変動がルートの構築に 与える影響を無視しているので、同じノード配置でもルーティングの実行時刻 によって異なるルートが構築される。無線バックホールの Static 型ルーティン グ手法において、システム起動時の伝搬路状況だけを見てルーティングを行う と、その後伝搬路が変動すれば、当該ルートによるシステムの性能が保証でき なくなり、最悪の場合中継経路が断絶される場合もある。文献[31]では独自の テストベッドを用いて無線バックホールにおける伝搬路の変動とルーティング 手法の関係について実験により調べ、従来の手法により構築されたルートは生 存期間が短く伝搬路状況に適応するために頻繁にルートを再構築する必要があ ることを示した。無線バックホールではシステムの起動時にルートを構築し、
そのあとは長時間変更しないためルートの頻繁な再構築は望ましくない。
第3章 無線バックホールにおける安定ルーティング手法 23
図 3.1 重み付きグラフ G
3.2
ルーティング手法におけるアルゴリズムとメトリック本節ではまず従来のルーティング手法におけるアルゴリズムとメトリックの 概要について説明し、次に本論文でルーティング手法の基礎としている最小伝 搬損ルーティング及びその問題点について説明する。
3.2.1
アルゴリズム無線バックホールにおけるルーティング手法はアルゴリズムとメトリックに より特徴つけられ、従来よく使われているルーティングアルゴリズムには
Bellman-Ford
アルゴリズムとDijkstra
アルゴリズムなどがある（[5], [3]）。Bellman-Ford
アルゴリズムとDijkstra
アルゴリズムはグラフ理論において単一始点の重み付きグラフにおける最短経路問題を解くアルゴリズムである（図 3.1）。 なおグラフの有向性と無向性は区別する必要がない。
Bellman-Ford
アルゴリズム は負の重みを持つグラフにも対応しているのに対し、Dijkstra
アルゴリズムは非 負の重みを持つグラフだけを対象にしている。Bellman-Ford
アルゴリズムにおい て非負の重みを持ったグラフだけに限定すると、Dijkstraアルゴリズムと近い手 法が使われる。本論文で検討している無線バックホールではメトリック、即ち グラフのエッジの重みはホップカウントなど正の値である。そのため以下では まず、Dijkstraアルゴリズムの動作について説明する。Dijkstra
アルゴリズムは図 3.1 に示すように、各辺が正の重みを持っているグラフ G に対し、始点ノードから各ノードまでの距離、即ち経路上の重みの和が 最小になるような経路を探す手法である。
Dijkstra
アルゴリズムは次のように表 現できる。第3章 無線バックホールにおける安定ルーティング手法 24
1. 初期化：始点ノードの値（コスト）は０、その他のノードの距離は∞に設定する。
2. 確定すべきノードがなくなるまで以下の処理を繰り返す：
1) 現時点で始点ノードまでの最短経路が確定されていないノードのうち、最小の 値を持つノードを見つけ、確定ノード（決定された）とする。
2) 確定ノードからエッジが伸びているノードをそれぞれチェックし、「確定ノード のコスト（始点ノード間での経路上の重みの和） ＋ エッジのコスト（重み）」
を計算し、そのノードの保持している値より小さければ、値を更新し、経路情 報即ち「上り中継先」を確定ノードを指すようにする。
以下では図 3.1 のグラフ
G
を用いてDijkstra
アルゴリズムの動作について詳 しく説明する。なお動作途中確定されたノードは赤色で示す。まずアルゴリズムの最初のループで始点ノード自身が確定されるので、図
3.1.1
のような状態になり、始点ノード０が赤い色になる。次に始点ノードからエッジが伸びているノード１、２、３の値（始点ノードまでの重みの和）２、
４、５を計算し（青い色）、経路変数もそれぞれ始点ノード０を指すようにし、
図
3.1.2
の状態になる。次に
2
回目のループで始点ノードまでの距離が最短であるノード１が選択さ れ、確定される（図3.1.3）
。このときノード１からエッジが伸びているノード０、２、４の距離も計算されている。但しこの場合始点ノードへ戻る経路は意味が ないので破棄する（最短経路にはなれないから）。更にこのときノード２では値 ４と値５が現れるが、大きい値である５は破棄され、経路は更新されない。な おノード４では経路が更新され値が８（もともとは∞）、上り中継ノードはノー ド１とされ、最終的に図
3.1.4
の状態になる。3
番目のループで、始点ノードまで最短距離を持つノードとして、ノード２が 選択され、確定される。そしてノード２からエッジが伸びているノード３、１、４（始点ノードは除く）で、ノード２を経由する経路のコストがそれぞれ
6, 7, 8
と計算され、図3.1.5
になる。ここで新しく計算されたコストは緑色に表示する。更にノード３、１、４では新たに計算された値と保持していた値が比較され、
ノード３とノード４で経路情報が更新され図
