博士（情報科学）能代 学位論文題名
愛
ランダム 区間グ ラフに基づくアドホックネットワークの 連結性 に関する解析
学位論 文内容の要旨
近年，ノートPCやPDA，携帯電話をどのモバイル端末が急速に普及し，固定通信においては高速 常時接続のブロードバンドネットワークが広く導入されている．また，あらゆる物に通信機能を持つ チップが組み込まれ，相互に通信したり，既存のネットワークと接続することが可能をシステムが実 現しつっある．しかしこのように急速に高度化が進む通信技術においても，空間的・地理的制約，通 信対象の制約をど，その能カや仕様から生じる様々を制約が残っている．これらの制約を解消するた め に は， 従 来 の ネッ ト ワ ー クと は 異 を る新 た を 形 態の ネ ッ ト ワー ク が 必要と をって いる．
そのようを新た顔形態のネットワークとして，交換機や基地局等のインフラストラクチャに依存 せず，交換機能を持つ端末のみで構成される自律分散型ネットワークであるアドホックネットワー クが注目されている．アドホックネットワークにおける技術的課題は多く存在し，特にネットワーク 上でマルチホップ通信によって2端末間をっをぐ経路の存在確率，すをわち連結性を解析する必要 がある．一般に端末は2次元空間に配置されると考えられる．都市内では，端末が密に存在するので，
任意 の2端末 間の経 路の存在確率は1とみをすことができる．これに対し都市間では。端末の存在 は疎であるが，多くの場合1次元空間とみをすことができる，このようを観点から，1次元アドホッ クネットワークの連結性の解析は重要を課題とをっている，
1次元 アドホ ックネ ットワ ークモ デルと しては，2次元のランダムグラフモデルの1つである固 定半径モデル（単位円板グラフ，ランダム幾何グラフともいう）を1次元に縮退したモデルであるラ ンダム区間グラフ(Random Interval Graph:RIG)が知られている.RIGは何らかの確率分布に従って 1次元 ユーク リッド 空間上 にラン ダムに 配置され たn個の 頂点と ，互いの距離がR以内である2頂 点間に生成される辺によって構成されるグラフであり，全ての移動端末が距離R以内にある他の端 末と通信できる1次元アドホックネットワークの自然を数理モデルと考えられている．これに基づ いた1次元の 特定の モデル（本論文で扱うモデルの1つである自由端RIG)については，統計学の分 野での関連研究においてもすでに解析解が得られている．しかし，限定的教モデルであるため，アド ホックネットワークの連結性の解析には応用されず，それをさらに複雑化したネットワークについ ては，まだ解が求められていをかった．
本論 文では ，このよう教問題を解決するために従来の「自由端RIG」とは異をる「固定端RIG」 というモデルを提案し，その連結性について確率論に基づぃた厳密を解析解を数理的に求めている．
このモデルをピルディングプロックとすることによって，自由端RIGだけではをく，本論文で導入 する種々の複雑誼ネットワークの解析解も求めている．
本論文は全6章で構成され，その内容は以下の通りである，
‑ 1445−
第1章 の 序 論 にお い て ， 本 研究 の 背 景 及 び目 的 に つ い て 述べ て い る ． 第2章 で は ， 第3章 以 降 の準 備 と して ， ア ド ホ ッ クネ ッ トワ ークと それ に関連 する技 術，ラ ンダ ムグラ フ，順 序統計 量につ いて 概 説 し て い る ， ま た ， 本 論 文 の 関 連 研 究 に つ い て も 概 観 し ， 本 論 文 の 特 徴 を 明 確 に し て い る ． 第3章 に お い ては ， ま ず 本 論文 で 提 案 す る「 固 定 端RIG」 の 定 義 を述 べ て い る ．こ れ は ，1次元 の 有 限 空間 内 に 一 定 数 の頂 点 が 一 様 分布 す る 条 件 の下 で ， 区 間 の両 端 に 必 ず頂点 が存在 するモ デル で あ る ，こ の モ デ ル は ，次 章 で導 入する すべ ての派 生モデ ルの基 本と をるモ デルで あり， 本論文 にお い て 中 心と を る モ デ ル であ る ， 次 に 固定 端RIGが 連 結 グ ラ フ であ る 確 率 が 満た す べ き 再 帰的 を 積 分方 程 式 を示 し ， そ の 積 分方 程 式の 特徴に つい て詳細 に述べ ている ．ま た，積 分方程 式によ って導 き出 さ れ る 解の 係 数 が す べ て整 数 に社 ること を示 し，係 数のみ を求め る漸 化式を 導出し ている ．最後 に， 再 帰 的 を積 分 方 程 式 で 表さ れ た解 にラプ ラス 変換を 導入す ること によ り，そ の閉じ た解を 求めて いる ． 第4章 で は ， 固 定 端RIGか ら 派 生 す る7つ の モ デ ル と し て ， 自 由 端RIG， リン グ モ デ ル ，固 定 端 イ ン フラ モデル ，中継 端末チ ェー ンモデ ル，中 継イン フラ スター モデル ，2端末間 通信モ デル， 部分 区 間 通 信 モ デ ル を 導 入 して い る ， 「 自由 端RIG」は ， 固 定 端RIGの 定 義 から 区 間 の 両 端に 頂 点 が 存 在 す る とい う 条 件 を 取 り除 い た モ デ ルで あ る ． こ のモ デ ル で は ，固 定 端RIGの 結 果 を 利 用す る こ とに よ っ て， そ の 連 結 確 率を 解 析 的 に 示し ， ラ プ ラ ス変 換 を 導 入 する こ と に よって 閉じた 解を求 めて い る， 「リン グモデ ル」 は，区 間の代 わりに りング（円周）上にランダムに頂点を配置するモデルである．
こ の モデ ル で は ， 固 定端RIGの結 果 を 利 用 して ， そ の連結 確率 を解析 的に示 し，ラ プラ ス変換 を導入 する ことに よって 閉じ た解を 求めて いる． 「固 定端イ ンフラ モデル 」，「 中継 端末チ ェーンモデル」，
「 中 継イ ン フ ラ ス タ ーモ デ ル 」 の3つ の モ デ ル は， 実際 のアド ホッ クネッ トワー クの利 用形態 を考 慮 し ， 固定 さ れ た 中 継 用の 端 末や ，有線 でっ をがれ たイン フラ設 備を 取り入 れたモ デルで ある， これ ら の モ デル で は ， 固 定 端RIG， 自由 端RIG，リ ン グ モ デ ルの 結 果 を 利 用す る こと によっ て，そ れらの 連 結 確 率の 解 析 解 を 求 めて い る． 「2端末間 通信モ デル 」は，1次 元アド ホック ネット ワー クにお いて，
区 間 内 の 任 意 の2端 末間 の 連 結 性 に着 目 し た モ デル で あ る ． こ のモ デ ル で は ，区 間 内 の 任 意の2端 末 間 の連 結 確 率 を 解 析的 に 求 め て いる ． 「 部 分 区間 通信 モデル 」は，1次 元アド ホック ネット ワー ク に お いて ， あ る 部 分 区間 に 存在 する端 末間 の連結 性に着 目した モデ ルであ る．こ のモデ ルでは ，部 分 区 間 内 の 距 離 が 最 も 離れ た2端 末 間の 連 結 確 率 を解 析 的 に 求 め てい る ． を お 最後 の2つ の モデ ル で は ， 区 間 ま た は 部 分 区 間 内 の 任 意 の2端 末 間 の 連 結 性 の 解 析 解 を 求 め て い る ． 第5章 で は ， 本論 文 の 成 果 を視 覚 的 に 検 証し ， 普 及 さ せ るた め に 作 成 した ソ フ ト ウ ェア に つ いて 述 べ てい る ． モ デ ル の種 類 ，端 末数， 区間 長など を入カ すると ，導 出され た式と そのグ ラフが 出カ さ れ る ．こ の ソ フ ト ウ ェア を 利 用 す るこ と に よ っ て， 本 論 文 で 求め た8つ の モデ ル に 基 づ ぃ た連 結 性 の検 証をイ ンタラ クテ ィプに 行うこ とがで きる ，
最後 に第6章で ，本 研究の 成果と 今後の 課題を まと めてい る．
―1446−
学位論文審査の要旨 主査 助教授 野中秀俊 副査 教授 宮 腰政明 副査 教授 工 藤峰一 副査 教授 佐 藤義治 副査 教授 栗 原正仁
学 位 論 文 題 名
ランダム区間グラフに基づくアドホックネットワークの 連結性に関する解析
近年ノ ートPCやPDA，携帯 電話を どのモ バイル端末が急速に普及し，固定通信においては高速 常時接続のプロードバンドネットワークが広く導入されている。また，あらゆる物に通信機能を持 つシステムが組み込まれ，相互に通信することが可能をシステムが実現しつっある。しかしこのよ うに急速に高度化が進む通信技術においても，空間的・地理的制約，通信対象の制約をど，その能カ や仕様から生じる様々を制約が残っている。これらの制約を解消するためには，従来のネットワー クとは異をる新たを形態のネットワークが必要となっている。
そのようを新たを形態のネットワークとして，交換機や基地局等のインフラストラクチャに依存 せず，交換機能を持つ端末のみで構成される自律分散型ネットワークであるアドホックネットワー クが注目されている。アドホックネットワークにおける技術的課題は多く存在し，特にネットワー ク上でマルチホップ通信によって2端末間をっをぐ経路の存在確率，すなわち連結性を解析する必 要がある 。一般 に端末 は2次元 空間に 配置されると考えられる。都市内では端末が密に存在する ので，任 意の2端 末間の経路の存在確率は1とみをすことができる。これに対し都市間では端末の 存在は疎であるが，多くの場合1次元空間とみをすことができる。このようを観点から，1次元アド ホ ッ ク ネ ッ ト ワ ー ク の 連 結 性 の 解 析 は 重 要 を 課 題 で あ る と 考 え ら れ る 。 1次元ア ドホッ クネットワークモデルとしては，何らかの確率分布に従って1次元ユークリッド 空間上に ランダ ムに配 置され たn個の 頂点と ，互い の距離 がR以内 である2頂点間 に生成さ れる 辺によって構成されるグラフであるランダム区間グラフ(Random Interval Graph: RIG)が知られて いる。こ れは全 ての移 動端末 が距離 尺以内 にある他の端末と通信できる1次元アドホックネット ワークの自然を数理モデルであると考えられている。これに基づぃた1次元の特定のモデル（本論 文で扱う モデル である 自由端RIG及び固 定端RIG)と等価をモデルについては，それぞれ統計学及 び優生学(eugenics)の分野において解析解が得られている。しかし，いずれも個別限定的をモデル であり，また導出過程が陽に示されていをいため，多様謡アドホックネットワークの連結性の解析に 直接適用することは困難であった。また複雑化したネットワークについては，まだ解が求められて
い橡かった。
本論文では。このよう顔問題を解決するために「固定端RIG」というモデルを提案し，その連結性 につ いて確 率論に 基づぃた厳密を解析解を数理的かつ構成的に導出している。このモデルをビル ディ ングブ ロック とすることによって，本論文で導入する様々をモデルの解析解も求めている。
論文 は全6章 で構成されている。第1章は序論であり，本研究の背景及び目的について述べてい る。第2章では，第3章以降の準備として，アドホックネットワークとそれに関連する技術，ランダ ムグラフ，順序統計量について概説している。また，本論文の関連研究についても概観し，本論文の 特徴を明確にしている。
第3章 では， 本論文 で提案 する「 固定端RIG」を定義している。固定端RIGが連結グラフである 確率が満たすべき再帰的を積分方程式を示し，その積分方程式の特徴について詳細に述べている。
また．積分方程式によって導き出される解の係数がすべて整数にをることを証明し，係数を求める漸 化式を導出している。最後に，再帰的を積分方程式で表された解にラプラス変換を導入することに より，その閉じた解を求めている。
第4章 では， 固定端RIGから派生する7個のモデルとして，自由端RIG，リングモデル，固定端イ ンフラモデル，中継端末チェーンモデル，中継インフラスターモデル，2端末間通信モデル，部分区間 通信モデルを導入している。各モデルについて，固定端RIGの結果を用いることによって連結グラ フである確率を解析的に求めている。
第5章では，以上の成果を視覚的に検証し，普及させるてとを目的として作成したソフトウェア について述べている。このソフトウェアを利用することによって，本論文で求めた8個のモデルに 基 づ ぃ た 連 結 性 の 検 証 を イ ン タ ラ ク テ ィ ブ に 行 う こ と が で き る こ と が 確 認 さ れ た 。 これらの研究成果の評価すべき点はっぎのようにまとめられる。
1．アドホックネットワークにおける現実的問題に即した8つの連結性解析モデルを提示し，その厳 密解を解析的に導出している点に新規性が認められる。
2．その解析手法は工業数学的手法を用いた機械的を数式計算に基いており，それによって，研究分 野と証明方法の異をる既存の結果を含むすべての結果を統一的に導出している点に科学的を有用性 が認められ，また，それらの解析解の視覚的な検証を可能とするシステムを開発した点について，産 業的を有用性が認められる。
これを要するに，著者は，アドホックネットワークの連結性の解析について新知見を得たものであ り，数理情報科学とその応用に対して貢献するところ大をるものがある。よって著者は，北海道大学 博士（情報科学）の学位を授与される資格あるものと認める。
―1448ー
