はじめに
近年，フィーチャーフォンからスマートフォンが使われるようになり，2013年から2018年にかけて世界のモバイルデータのトラフィック量は年平均61%ずつ増えていくといわれている．そのため，通信ネットワークにおいて情報を効率良く送ることが必要とされる．2000年にAhlswedeらが『ネットワーク符号化』(以下，NCと略す)という通信ネットワーク上の新しい情報伝達の方法を提案した[1-18]．本来，通信ネットワークを伝達する情報は時々刻々と経路を伝わっていくが，既存の研究では時々刻々と情報が流れていくことが表わされていない．また，ネットワーク符号化を適用したネットワークにおいて，送信者が送信した情報はネットワーク構造により必ずしも所望の送信先に伝わるとは限らず，受信者はどの送信者が送信した情報を得られるかがわからない．そこで本研究では，時々刻々と情報が伝わるネットワークにネットワーク符号化を適用することを考え，そのネットワークにおいて情報を伝達する方法とそのネットワークにおいて受信者がどの送信者が送信した情報を受け取れるかを判定する方法を提案する．
先行研究
既存のネットワーク符号化
NCの考え方を説明する．ネットワーク内においてある送信者からある受信者へ情報を伝達したく，そのような送受信の組が複数個ある場合を考える．送信者と受信者の経路上にある中継地点は送られてきた情報に他の情報との符号化を施したり，符号化した情報と別の受け取った情報から元の情報を復元したりして、得た情報を次の中継地点に伝える。受信者は送られてきた情報から所望の情報を復元することで送信者が送信した情報を取得する。情報の符号化と復元を適切に行うことでネットワークの複数の送受信間で同時に情報を伝達することができ，ネットワーク内で効率的に情報を送ることができる．
 |
| 図1: 排他的論理和の性質 |
 |
| 図2: 既存のネットワーク符号化 |
図2のネットワークにおいてネットワーク符号化を適用しない場合を考えてみる．情報aを送る場合も情報bを送る場合もノードNcからノードNt3のエッジを使わなければならない．さらに，エッジには1ビットの情報しか送ることができず，情報aも情報bも1ビットの情報であるため，情報aまたは情報bのどちらかしか送ることができない．
NCは効率的に情報を伝達できる性質に加え，符号化した情報と復元するための情報がないと元の情報を復元できないことと符号化の方法を知らなければ元の情報を復元できないという理由から，NCは安全に情報を伝達できる性質がある[19-21]．また，NCの定式化が考えられた[22,23]．和を排他的論理和とし，積を論理積とした環を考え，その環上の行列を定義する．そして，受信者が受け取る情報をその行列を用いて表現し，その行列を使って情報を復元する方法が考え出された．
既存のネットワーク符号化の問題点
本来，送信者から受信者へ伝達する情報は時々刻々とネットワークの中継地点を伝わっていくが，既存の研究の定式化では情報がネットワーク内を時々刻々と伝わっていくことが表わされていない．時間を考慮したネットワークにNCを適用し，受信者が複数の中継地点から情報を受け取るとき，受け取った複数の時系列情報のうちどの情報を用いれば所望の情報を得られるかわからなくなってしまう．また，受信者が受け取った情報から所望の情報を復元できるかを判定する方法がわかっていない．NCを適用したネットワークでは，中継地点のサーバは受け取った情報に符号化や復元を施して次の中継地点や受信者に情報を送る．中継地点のサーバが受け取る情報の数が多くなると，その中継地点のサーバがどの情報を符号化したり，復元して次へ送るかという情報の送り方の数は多くなり，ネットワーク全体での情報の送り方は非常に多くなる．そのような非常に多い送り方の中で，NCを適用したネットワークにおいて複数の送受信間で同時に情報を伝達するような送り方を設計しなければならない．ネットワークの送り方を設計する際にそれぞれの受信者がどの情報を得るのかを判定する方法が必要となる．
入力可観測性
制御理論において出力から入力を求める研究が行われている[24-32]．線形の状態方程式で表現されたシステムにおいて，システムの全出力からシステムの全入力を得ることができる入力可観測性という性質を考え，システムが入力可観測であるための必要十分条件が導出されている．
アプローチと研究結果
離散時間情報伝達ネットワーク系
 |
| 図3: 離散時間情報伝達ネットワーク系の例 |
離散時間情報伝達ネットワーク系を説明する．例として図2でのネットワーク構造の離散時間情報伝達ネットワーク系を説明する．このネットワークにおいて，ノードNs1からノードNr2へそれぞれ1ビットの情報a0, a1, ...を送り，ノードNs2からノードNr1へそれぞれ1ビットの情報b0, b1, ...を送ることを考える．ノードNs1とノードNs2が時刻kに送信する情報を図3の下の表に示す．ノードNsiが時刻kに送信する情報をノードNsiを始点とするエッジに持たせる．例えば時刻0のとき，ノードNs1が送信する情報a0をノードNs1を始点とするエッジに持たせる．また，ある時刻にあるエッジに持たせた情報は次の時刻にエッジの向きに伝わる．例えば，時刻0にノードNs1を始点とするエッジに持たせた情報a0は時刻1のときノードNt1を始点とするエッジに持たせる．また，ノードNcを始点とするエッジには前の時刻にノードNt1を始点とするエッジにある情報とノードNt2を始点とするエッジにある情報の排他的論理和とする．そして，ノードNr1とノードNr2が各時刻に受け取る情報を図3の下の表に示す．例えば，ノードNr1は時刻1にノードNt1を始点とするエッジから情報a0を受け取り，時刻3にノードNt3を始点とするエッジから情報a0と情報b0の排他的論理和の情報を受け取る．ノードNr1とノードNr2が各時刻に受け取る情報から所望の情報を得る(ノードNs1からノードNr2へそれぞれ1ビットの情報a0, a1, ...を送り，ノードNs2からノードNr1へそれぞれ1ビットの情報b0, b1, ...を送る)ことを考える．
集合F
集合Fを0と1からなる集合とし，集合Fにおける加法を排他的論理和とし，乗法を論理積とすると，集合Fは体である．以降，状態方程式で使う行列とベクトルは集合F上の行列とベクトルである．
状態方程式を用いた情報復元
 |
| 図4: 排他的論理和の性質 |
ネットワーク符号化の手法を適用した離散時間情報伝達ネットワーク系において，システム行列を用いる情報の復元方法を提案する．まず，ネットワークを表現した有向グラフにおいて，送信者からいくつかの中継地点を経て受信者へ情報を送信することを考える．そして，すべての送信者が送る時系列情報をシステムの入力とし，ある受信者が受け取る時系列情報をシステムからの出力とし，ネットワーク符号化を適用した情報の流れを状態方程式で表現する．さらに，その状態方程式を用いて導出した出力の時系列データとシステム行列から入力の時系列データを求め，送信者が送信した情報を取得できる．
図3の離散時間情報伝達ネットワーク系を考える．ノードNs1とノードNs2が時刻kに送信する情報をそれぞれ入力u1(k)，u2(k)とし，ノードNs1を始点とするエッジとノードNs2を始点とするエッジそれぞれにu1(k)，u2(k)を持たせる．次にノードNs1を始点とするエッジとノードNs2を始点とするエッジ以外のエッジに状態量を持たせる．これらを用いて情報の流れを表現し，状態方程式で表現する．状態方程式で用いたシステム行列とノードNr1またはノードNr2が受け取る出力から入力を求める，つまり，ノードNs1とノードNs2が送信した情報を取得する．
部分的入力可観測性を用いた情報の可伝達性
部分的入力可観測性を用いて受信者が受け取る情報から所望の情報を取得できるかを判定する方法を提案する．まず，全ての入力のうち一部の入力を部分的入力と定義する．さらに，一つの受信者を選択し，その選択した受信者の出力からその部分的入力を取得できるという部分的入力可観測性を定義する．また，受信者での情報復元の過程からシステムが部分的入力可観測であるための必要十分条件を導出する．この必要十分条件に状態方程式のシステム行列を代入することで選択した受信者にどの情報が伝達するかを判別できる．
今後の目標
今後の課題はネットワーク符号化を適用可能な一般的なネットワークに対し，所望の情報を伝達できるような情報の送り方を設計することである．一つのアイデアとしてシステム同定の手法を用いる方法が考えられる．送信側が時々刻々と情報を送り，受信側が所望の情報を復元できるような出力を得る場合を考え，その入出力データから情報の送り方を定めることができると期待される．
参考文献
[1] R. Ahlswede and N. Cai and S. Y. R. Li and R. W. Yeung, "Network infomation flow," IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204--1216, 2000.
[2] Ho, Tracey and Lun, Desmond, Network coding: an introduction, Cambridge University Press, 2008.
[3] Chou, Philip A and Wu, Yunnan and Jain, Kamal, Practical network coding, Citeseer, 2003.
[4] Katti, Sachin and Rahul, Hariharan and Hu, Wenjun and Katabi, Dina and Médard, Muriel and Crowcroft, Jon, 2006.
[5] Ho, Tracey and Koetter, Ralf and Medard, Muriel and Karger, David R and Effros, Michelle, The benefits of coding over routing in a randomized setting, IEEE, 2003.
[6] Gkantsidis, Christos and Rodriguez, Pablo Rodriguez, 2005.
[7] Katti, Sachin and Rahul, Hariharan and Hu, Wenjun and Katabi, Dina and Médard, Muriel and Crowcroft, Jon, XORs in the air: practical wireless network coding, IEEE Press, 2008.
[8] Sanders, Peter and Egner, Sebastian and Tolhuizen, Ludo, 2003.
[9] M. Massoumnia and G. Verghese and A. Willsky, "Failure detection and identification," IEEE Trans. Autom. Contr., vol. 34, no. 3, pp. 316--321, 1989.
[10] Tateno, Terumasa and Matsumoto, Ryutaroh and Uyematsu, Tomohiko, "Decodability of Network Coding with Time-Varying Delay and No Buffering.," IEICE Transactions, vol. 92-A, no. 8, pp. 2141-2145, 2009.
[11] Wu, Yunnan and Chou, Philip A and Kung, Sun-Yuan and others, 2005.
[12] Katti, Sachin and Gollakota, Shyamnath and Katabi, Dina, 2007.
[13] Fragouli, Christina and Le Boudec, Jean-Yves and Widmer, Jörg, Network coding: an instant primer, ACM, 2006.
[14] Dimakis, Alexandros G and Godfrey, P Brighten and Wu, Yunnan and Wainwright, Martin J and Ramchandran, Kannan, Network coding for distributed storage systems, IEEE, 2010.
[15] Koetter, Ralf and Kschischang, Frank R, Coding for errors and erasures in random network coding, IEEE, 2008.
[16] Widmer, Jörg and Le Boudec, Jean-Yves, 2005.
[17] Wu, Yunnan and Chou, Philip A and Kung, Sun-Yuan, Minimum-energy multicast in mobile ad hoc networks using network coding, IEEE, 2005.
[18] Nguyen, Dong and Tran, Tuan and Nguyen, Thinh and Bose, Bella, Wireless broadcast using network coding, IEEE, 2009.
[19] Cai, Ning and Yeung, Raymond W, 2002.
[20] Ho, Tracey and Médard, Muriel and Shi, Jun and Effros, Michelle and Karger, David R, 2003.
[21] Ho, Tracey and Médard, Muriel and Koetter, Ralf and Karger, David R and Effros, Michelle and Shi, Jun and Leong, Ben, A random linear network coding approach to multicast, IEEE, 2006.
[22] S. Y. R. Li and R. W. Yeung and N. Cai, "Linear network coding," IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371--381, 2003.
[23] R. Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782--795, 2003.
[24] M. K. Sain and J. L. Massey, "Invertibility of linear time-invariant dynamical systems," IEEE Transactions on Automatic Control, vol. ac-14, no. 2, pp. 141-149, 1969.
[25] HARA, SHINJI, Unknown input observability for discrete-time linear multivariable systems and its application, Taylor & Francis, 1984.
[26] D. Cheng and H. Qi, "Controllability and observability of Boolean control networks," Automatica, vol. 45, pp. 1659--1667, 2009.
[27] D. Cheng and H. Qi, "A Linear Representation of Dynamics of Boolean Networks," IEEE Trans. Autom. Contr., vol. 55, no. 10, pp. 2251--2258, 2010.
[28] Cheng, Daizhan, Input-state approach to Boolean networks, IEEE, 2009.
[29] Cheng, Daizhan and Qi, Hongsheng and Xue, Ancheng, A survey on semi-tensor product of matrices, Springer, 2007.
[30] Cheng, Daizhan and Qi, Hongsheng, State--space analysis of Boolean networks, IEEE, 2010.
[31] Cheng, Daizhan and Qi, Hongsheng, A linear representation of dynamics of Boolean networks, IEEE, 2010.
[32] Cheng, Daizhan and Qi, Hongsheng, Controllability and observability of Boolean control networks, Elsevier, 2009.