無線通信網のリンクスケジューリング問題に対する二段階近似解法の提案
スポンサーリンク
概要
- 論文の詳細を見る
無線通信網では全局間が直接交信可能ではないため, 経路上の局を順次経由することにより, 転送元から転送先へのパケット転送が行なわれる.そのため, 複数の転送要求が与えられたとき, 総転送時間を最小化する通信経路の割当, および各局での転送タイミング(リンク)のスケジューリングが必要となる.本論文では, 後者のリンクスケジューリング問題に対する二段階近似解法の提案を行う.本問題は, 順序制約を有するSAS問題と有さないNAS問題で構成されており, いずれもNP困難であることが知られている.提案解法の第1段階では, Greedy法を用いて初期解を生成する.第2段階では, 制約未充足のリンクの強制割当の繰り返しにより解を探索する.NASおよびSASの双方における500局通信網までの例題に対するシミュレーションにより, 本提案解法の有効性を示す.
- 社団法人電子情報通信学会の論文
- 2000-03-22
著者
-
田島 滋人
大阪大学大学院基礎工学研究科
-
東野 輝夫
大阪大学基礎工学部情報科学科
-
東野 輝夫
大阪大学大学院情報科学研究科|独立行政法人科学技術振興機構 Crest
-
船曳 信生
大阪大学基礎工学部
-
田島 滋人
大阪大学基礎工学研究科情報数理系専攻
関連論文
- 無線メッシュネットワークのアクセスポイント間通信での優先度制御に関する一検討(フォトニックネットワークシステム,光ルーチング,ブロードバンドアプリケーション,一般)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムの改善(無線ネットワーク)
- 無線メッシュネットワークのアクセスポイント間通信での優先度順リンク動作方式(トラヒックエンジニアリング,一般,トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- 遷移の選択が状態訪問回数で決まる有限状態機械対からなる通信系に対する生存性の検証
- 通信プロトコルのLOTOS仕様から並行EFSM群への変換の一手法
- 遷移の選択が状態訪問回数に依存する有限状態機械対からなる通信系に対する生存性検証システム
- マキシマムニューロンを用いた安定結婚問題のニューラルネットワーク解法
- グループワークを考慮した協調計算システムにおける動作プログラム群の生成と分散実行
- 遷移条件が状態訪問回数に依存する有限状態機械の生存性検証
- 共有メモリ型並列計算機上での正則な項書換え系の一実装法
- 拡張有限状態機械とペトリネットを表示編集できるGUIツールの作成と応用例 (第54回全国大会 (平成9年前期 於 : 千葉工大) 大会優秀賞受賞論文 (11件)
- レジスタ付きペトリネットを用いた全体動作仕様から分散動作仕様の自動合成とその応用 (コンカレント・コラボレーション技術論文小特集)
- レジスタ付き時間ペトリネットで記述された分散システムの時間制約付き全体仕様からその時間制約を満たす各ノードの動作記述の自動導出(並列・分散)
- あるスタイルに基づく順序機械型記述における詳細化の正しさの証明方法
- 関係データベースを用いた在庫管理プログラムの記述とその詳細化の正しさの証明
- リンクの故障を考慮に入れた分散システムの動作仕様の自動導出
- ペトリネットモデルを用いたソフトウェアプロセスの記述とその分散実行制御
- レジスタを持つ自由選択ネットで記述された分散システムの要求仕様から各ノードの動作仕様の導出
- 協調計算システムの動作仕様群の分散実行系
- ASLプログラム開発システムにおける検証の自動化について
- 拡張有限状態機械で記述された協調計算プログラムとその実行系
- 順序機械型プログラムの階層的設計法と在庫管理プログラムの開発例
- 拡張有限状態機械モデルを用いた分散システムの要求仕様から各ノードの動作仕様の自動導出
- 部分項の評価順が指定できる項書換え系とその性質について(計算機構とアルゴリズム)
- 代数的言語ASLを用いた酒屋在庫管理の要求仕様記述
- 無線メッシュネットワークにおけるリンク動作率による固定待機時間切り替え方式の提案 (ネットワークシステム)
- 無線メッシュネットワークのWDSクラスタ分割問題
- 無線LANのWDSにおけるAP間通信へのリンクスケジューリングアルゴリズムの適用(有線/無線シームレスネットワーク, ネットワーク制御, 無線通信, モバイルネットワーキング, Mobile IP, 一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークのリンクスケジューリング問題に対するヒューリスティック解法の提案(無線・モバイルネットワーク)(ブロードバンドネットワークサービス)
- 静的及びモバイルマルチキャストルーチング問題に対する最適パス選択解法の提案
- 双方向マンハッタンストリートネットワークのノード配置問題に対する階層型近似アルゴリズムの提案
- ネットワークのリンクスケジューリングへのグラフ彩色アプローチ
- 無線通信網のリンクスケジューリング問題に対する二段階近似解法の提案
- 無線通信網における信頼度制約通信経路割当問題に対するニューラルネットワーク併用2段階解法の提案
- 安定結婚問題を対象とした離散型ニューラルネットワーク解法の性能評価
- 安定結婚問題のニューラルネットワーク解法の提案
- in-order実行パイプラインCPUの正しさの自動証明例
- FDTって何?(コンピュータと通信)
- すべての変数が存在記号で束縛された冠頭標準形プレスブルガー文の真偽判定の高速化手法
- プレスブルガー文真偽判定手続きを用いた算術演算回路の正しさの証明
- プレスブルガー文真僞判定手続きを用いた算術演算回路の正しさの証明
- 時間拡張LOTOSの処理系を用いたSMIL記述の実行とQoS制御
- 時間拡張LOTOSの処理系を用いたSMIL記述の実行とQoS制御
- マルチランデブを用いたLOTOS仕様の実行の可視化 (マルチメディア通信と分散処理)
- LOTOSで記述されたプロトコルの実行の可視化
- イベントとアニメーション表示の対応付けによるLOTOSプログラムの実行の可視化
- ゲートウエイにMIMOチャネルを用いた無線メッシュネットワークでのWDSクラスタ分割アルゴリズム (ネットワークシステム)
- 入力が競合する有限状態機械群からなる通信ソフトウェアの適合性試験に一手法
- 複数個のFSMからなるプロトコル機械に対する適合性試験の一手法
- あるクラスの時間オートマトンに対する適合性試験系列生成の一手法(マルチメディア通信と分散処理)
- 並行EFSM群でモデル化された通信プロトコル動作仕様のハードウェア実現とマルチランデブ制御機構
- 代数的手法を用いたCPU KUE-CHIP2の段階的設計の正しさの自動証明
- 代数的手法を用いたパイプライン方式CPUの設計検証
- 代数的手法を用いたCPU KUE-CHIP2の段階的設計およびその正しさの証明
- 代数的言語ASLによる回路設計支援システムにおけるSFL記述への詳細化とその変更及びそれらの正しさの検証
- FORTE/PSTV'97(形式記述技法と通信プロトコルに関する合同国際会議)報告
- Joint International Conference on Formal Description Techniques IX, and Protocol Specification, Testing, and Verification XVI (FORTE/PSTV 96)
- FORTE/PSTV '98 : 形式記述技法と通信プロトコルに関する合同国際会議 参加報告
- 代数的仕様から関数型プログラムの導出とその実行 (関数型プログラミングとその応用)
- 会議レポート ICNP'98 (IEEE主催第6回ネットワークとプロトコルに関する国際会議)報告
- 分散環境でのLOTOS仕様の実現とその評価(マルチメディア通信と分散処理)
- 周期スレッドを用いた実時間LOTOSコンパイラの設計
- マルチスレッド化された目的コードを生成するLOTOSコンパイラの実現 (マルチメディア分散・協調コンピューティング)
- マルチランデブを用いた分散システムの記述とバス結合ネットワーク上での実行
- in-order実行パイプラインCPUの正しさの自動証明例
- バス結合型ネットワーク上でのマルチランデブの実現法
- 時間制約の記述されたLOTOS仕様からのプロトコル合成 (マルチメディア通信と分散処理)
- 時間値による状態爆発を回避した時間的双模倣等価性検証法(計算モデルと計算の複雑さに関する研究)
- 拡張有限状態機械モデルで書かれた通信プロトコルの適合性試験系列の自動生成の一手法
- マルチスレッド化目的コードを生成するLOTOSコンパイラの機能拡張
- 隣接しない動作間の時間制約を記述するためのLOTOS言語の拡張とその等価性の検証
- 代数的言語で記述した抽象的順序機械型プログラムの設計検証の自動化
- マルチスレッド化目的コードを生成するLOTOSコンパイラの評価
- 全ての変数が存在記号で束縛された冠頭標準形プレスブルガー文の真偽判定プログラム
- 時間制約付LOTOSで記述された分散システムの全体仕様から各ノードの動作仕様の自動生成
- LOTOSによるソフトウェアプロセスの記述とその実行
- 整数上の論理式の恒真性判定アルゴリズムを用いた組合せ論理回路の実現の正しさの証明
- マルチスレッド化されたオブジェクトコードを生成するLOTOSコンパイラの試作
- 拡張有限状態機械モデルにおける通信プロトコルのテスト系列の自動生成の一手法
- LOTOS風言語で書かれた同期式順序回路の要求仕様記述と回路自動合成
- 時間制約付LOTOSの等価性の証明(計算量理論)
- 代数的手法を用いた同期式順序回路の段階的設計法
- 拡張有限状態機械モデルで書かれた通信プロトコルの適合性試験系列の自動生成の一手法
- 並列実行される動作におけるデータ代入の衝突の判定
- ゲートウェイにMIMOチャネルを用いた無線メッシュネットワークでのWDSクラスタ分割アルゴリズム(トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- 無線メッシュネットワークにおけるリンク動作率による固定待機時間切り替え方式の提案(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークのためのQualNetでの固定バックオフ時間切替方式の実装と評価(コア・メトロシステム,フォトニックネットワーク・システム,光ネットワーク運用管理,光ネットワーク設計,トラヒックエンジニアリング,シグナリング,GMPLS,ドメイン間経路制御,ネットワーク監視,イーサネット,光伝達網(OTN),高速インタフェース,光制御(波長変換・スイッチング・ルーチング),光ノード技術,光クロスコネクト(OXC),光分岐挿入多重(OADM),光多重・分離装置,光信号処理光スイッチ素子,一般)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムのスマートアンテナ拡張の一般化 (ネットワークシステム)
- 無線メッシュネットワークでの2個のスマートアンテナ使用アクセスポイントを有するWDSクラスタへの分割アルゴリズム(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークでの2個のスマートアンテナ使用アクセスポイントを有するWDSクラスタへの分割アルゴリズム(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- An Extension of Wireless Internet-Access Mesh Network Simulator for Smart Antenna Use and Evaluations Using Simple Topologies (ネットワークシステム)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムのスマートアンテナ拡張の一般化(トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- 無線メッシュネットワークでの2個のスマートアンテナ使用アクセスポイントを有するWDSクラスタへの分割アルゴリズム
- 無線メッシュネットワークでの2個のスマートアンテナ使用アクセスポイントを有するWDSクラスタへの分割アルゴリズム
- WIMNETシミュレータのスマートアンテナ利用への拡張と単純トポロジでの評価(一般,ネットワークアーキテクチャ(オーバレイ,P2P、ユビキタスNW,スケールフリーNW,アクティブNW,NGN・新世代NW),次世代パケットトランスポート(高速Ethernet,IP over WDM,マルチサービスパケット技術,MPLS),グリッド,一般)
- 無線メッシュネットワークのための固定バックオフ時間切替方式のLinux実装設計(ポストIPネットワーキング,新世代ネットワーク,ネットワークモデル,インターネットトラピック,TCP/IP,マルチメディア通信,ネットワーク管理,リソース管理,プライベートネットワーク,NW安全性及び一般)
- 無線メッシュネットワークにおけるリンク速度を考慮したクラスタ分割アルゴリズム(無線分散ネットワーク,M2M (Machine-to-Machine), D2D (Device-to-Device),一般)