確率的組合せ論のＸ符号及び類似の離散構造への応用

随机组合学在 X 代码和类似离散结构中的应用

基本信息

批准号：
18J20466
负责人：
角田有
金额：
$ 1.6万
依托单位：
Chiba University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-25 至 2021-03-31
项目状态：
已结题

项目摘要

本研究では、数学の一分野である確率的組合せ論を用いて、X符号をはじめとする種々の組合せ構造について理論的に明らかにすることを目的としている。本年度は、前年度までの研究で、X符号の圧縮比に関する限界式の導出や構成アルゴリズムを考案する際に用いた確率的証明や確率的証明の脱乱択化の手法を、グラフ理論における概支配集合や無線通信のスペクトラム拡散における周波数ホッピング系列に応用し、次の研究成果を得た。まず、グラフの概支配集合とは、支配集合という無線通信ネットワークやセンサーネットワークなど様々な応用先のあるグラフの頂点集合を一般化した集合であるが、他の条件が同じであればその集合の大きさは、小さいことが望ましい。本研究では、概支配集合の大きさをどこまで小さくできるのかの解析のため、その要素数に関する限界式を確率的証明によって新たに導出した。また、導出した限界式を満たす概支配集合の構成アルゴリズムを考案した。このアルゴリズムは、入力として対象のグラフを必要としないという驚くべき特徴を持ち、この特徴により、この構成アルゴリズムはネットワークのトポロジーが刻一刻と変化するセンサーネットワークへの適用性に優れている。次に、周波数ホッピング系列については、既存の研究では代数学的視点による抽象化が自然であるため、代数学的手法に大きく偏っており、代数学が特に有効であるような、限られた状況のみが考察されている場合が多いのだが、本研究において、周波数ホッピング系列に対しても確率的組合せ論を用いて、既知の限界式を改良することができている。X符号に関する研究結果が概支配集合や周波数ホッピング系列に関する研究に発展したように、本研究による理論的考察とその結果の影響は他分野にも広く波及すると期待される。

本研究的目的是使用随机组合学（数学的一个分支）从理论上阐明包括 X 代码在内的各种组合结构。今年，在我们去年的研究中，我们将介绍图论中概率证明的概述和概率证明的去随机化方法，这些方法在推导X代码压缩比的极限公式和设计构造时使用将该方法应用于无线通信中的优势集跳频序列和扩频，得到了以下研究成果。首先，图的近似支配集是对支配集进行概括的集合，支配集是具有诸如无线通信网络和传感器网络之类的各种应用的图的顶点的集合，其尺寸最好较小。。在本研究中，为了分析近似主导集的大小可以减少到什么程度，我们利用概率证明推导了一个关于元素数量的新极限公式。我们还设计了一种算法来构造满足导出的极限公式的近占优势集。该算法有一个令人惊讶的特点，即它不需要目标图作为输入，这一特点使得该构造算法非常适用于网络拓扑随时变化的传感器网络。接下来，关于跳频序列，现有的研究倾向于从代数的角度进行抽象，因此严重偏向于代数方法，并且只有在代数特别有效的有限情况下，很多情况下才考虑跳频序列。，但在这项研究中，即使对于跳频序列，我们也能够使用随机组合来改进已知的极限公式。正如X-code的研究成果已经发展为近似支配集和跳频序列的研究一样，这项研究的理论思考和结果有望广泛推广到其他领域。