無線ネットワークにおけるチャネル割当に対応したグラフ彩色について

田村 裕  松本 峻  中野 敬介  仙石 正和  

誌名
電子情報通信学会論文誌 A   Vol.J102-A   No.7   pp.214-223
発行日: 2019/07/01
Online ISSN: 1881-0195
DOI: 
論文種別: 論文
専門分野: グラフとネットワーク
キーワード: 
無線通信,  チャネル割当,  グラフ彩色,  Grundy Number,  

本文: PDF(1.6MB)>>
論文を購入




あらまし: 
無線通信におけるチャネル割当とグラフ理論における彩色問題は古くから関連性が示され,様々な研究がなされてきた.その中で多くの理論的な研究は,割当てるチャネル数を最小としたものである.これは,彩色問題における染色数(最小色数)に対応するからであり,グラフ理論における結果も応用可能であることからである.ただし,チャネル数を最小にするためには,全ての既に割当てられているチャネルを再割当する等,実際に適用するには問題が多い.そこで,準備するチャネル数の目安として,点や辺への彩色順によって色数が変化する際の最大値に注目し,その最大値を実現するグラフと彩色順について考察する.また,チャネル割当において,終了する通信に対応する新たな彩色問題を提案し,こちらの場合も色数最大となるグラフと彩色順について考察する.結果として,グラフを木に限定した場合に,これまでの彩色問題との違いを示す.