無線分散計算機ネットワーク上の高速通信アルゴリズムに関する研究

无线分布式计算机网络高速通信算法研究

• 批准号: 08680372
• 负责人: 藤田 聡
• 金额: $ 0.77万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08680372/
• 关键词: ネットワーク; 通信アルゴリズム; 無線通信; 並列アルゴリズム; 分散アルゴリズム; バスネットワーク

研究実績の概要は以下の通りである。1.無線ネットワーク上の周波数割当問題をネットワーク上の資源割当問題として定式化し、その計算複雑さについてあきらかにした。特に、与えられたネットワークの各ノードの次数が3に制限されたようなネットワーク(cubic graph)上での割当問題について深く考察し、各ノードに割り当てることのできる周波数を1からmに増加させることにより、各周波数がすべてのノードをカバーするという制約のもとで使用可能な周波数の種類が、mに関して超線形に増加することをあきらかにした(この結果については学術論文誌に投稿中)。2.無線ネットワークは、各送信ノードが複数の受信ノードに単位時間で情報を散布できるという観点から、一種のバスネットワークであるとみなすことができる。我々は各バスに接続されているノード数(無線ネットワークにおける各ノードの次数)が高々l(≧1)であるような(完全結合された)バスネットワークに着目し、そのようなネットワーク上での効率的な全対全通信(gossip)アルゴリズムを開発した(研究発表論文1)。3.無線ネットワークにける情報共有方式を提案した(研究発表論文2)。提案方式では、構成要素(ネットワークのノード)が動的に変化するような集合の共有を無線ネットワーク上でより少ないメッセージのやりとりで実現することができる。提案方式の基本的なアイデアは、共有される情報を連結リスト構造を用いて分散的に保持し、共有情報への各アクセスごとに連結リストの圧縮(path compression)をおこなうことである。提案方式のメッセージ複雑さは、ならし計算量によって評価されている。

Study the summary of the following general information. 1. When the number of cycles is cut when the problem is not available, the resource is cut when the problem is fixed, and the data is calculated to copy the data. The number of times per week is limited to 3 times per week. There is an in-depth investigation of the problem on the cubic graph, and the number of waves per cycle is increased. The number of waves per week

项目成果

Sotoshi Fujita: "A Gossip Algorithm for Bus Networks with Buses of Limited Length" Lecture Notes in Computer Science. 1123. 353-360 (1996)

Sotoshi Fujita：“具有有限长度总线的总线网络的八卦算法”计算机科学讲义。