(57)【要約】【課題】本発明は、ルーティングノード位置確定方法、装置及び端末装置を提供する。【解決手段】前記方法は、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；及び、前記所定条件を満足したルーティングノードデプロイメント案集合から、ルーティングノードデプロイメント案を選択することを含む。【選択図】図１５
2018056989.tif 000002
【特許請求の範囲】
【請求項１】
ルーティングノード位置確定装置であって、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成するための初期化モジュール；
第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算するための評価モジュールであって、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数である、評価モジュール；
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成するための処理モジュール；及び
前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択するための第１確定モジュールを含む、装置。
【請求項２】
請求項1に記載の装置であって、
前記評価モジュールは、前記各ルーティングノードデプロイメント案中のルーティングノード数量、及び、各センサノードからゲートウェイノードまでの第１最小コスト経路と、各センサノードから前記ゲートウェイノードまでの第２最小コスト経路とのルーティングコストの差に基づいて、前記各ルーティングノードデプロイメント案の適応度を計算し；
前記第１最小コスト経路は、前記ルーティングノードデプロイメント案中のルーティングノード位置範囲内のルーティングノードを通過し、前記第２最小コスト経路は、全てのデプロイメント可能なルーティングノード範囲内のルーティングノードを通過する、装置。
【請求項３】
請求項2に記載の装置であって、
前記評価モジュールは、
【数１】
2018056989.tif 000006
を用いて、前記各ルーティングノードデプロイメント案の適応度Fを計算し、
そのうち、｜I|は、前記ルーティングノードデプロイメント案中のルーティングノードの数量であり、｜PS|は、ネットワーク中のセンサノードの個数であり、liは、前記第１最小コスト経路のルーティングコストであり、li′は、前記第２最小コスト経路のルーティングコストであり、λは、ルーティング経路長さとルーティングノード数量の関係を調整するために用いられるものであり、iは、1からSまでの間の整数である、装置。
【請求項４】
請求項1に記載の装置であって、
前記所定条件は、j+1が第１閾値Nに等しいことであり、そのうち、Nは、1以上の整数であり、
前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足した時に、前記評価モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記第１確定モジュールは、前記適応度が最小のルーティングノードデプロイメント案を最終的なルーティングノードデプロイメント案と確定し、
前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足しない時に、前記評価モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記処理モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度に基づいて、前記第j+1世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+2世代ルーティングノードデプロイメント案集合を生成する、装置。
【請求項５】
請求項1に記載の装置であって、
前記初期化モジュールは、
リンク接続関係に基づいて、各センサノードから前記ゲートウェイノードまでの最小コスト経路を計算するための計算モジュール；
全ての前記センサノードが前記最小コスト経路を有する時に、各最小コスト経路上のデプロイメント可能なルーティングノード位置集合を１つのルーティングノードデプロイメント案とするための第２確定モジュール；及び
前記１つのルーティングノードデプロイメント案中のデプロイメント可能なルーティングノードの位置を前記リンク接続関係から除去し、更新後のリンク接続関係を生成し、これにより、前記初期化モジュールに、更新後のリンク接続関係に基づいて、次の１つのルーティングノードデプロイメント案を生成させるための更新モジュールを含む、装置。
【請求項６】
請求項5に記載の装置であって、
前記第２確定モジュールは、全てのセンサノードの中で前記最小コスト経路を有しないセンサノードがある時に、その前に得られたルーティングノードデプロイメント案集合を第0世代ルーティングノードデプロイメント案集合とする、装置。
【請求項７】
請求項1に記載の装置であって、
前記処理モジュールは、
第j世代ルーティングノードデプロイメント案集合から適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択して、第１ルーティングノードデプロイメント案集合を得るための選択モジュール；
前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対してペアリング・交叉処理を行うためのペアリング・交叉モジュール；及び
ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行って、前記第j+1世代ルーティングノードデプロイメント案集合を得るための変異モジュールを含む、装置。
【請求項８】
請求項7に記載の装置であって、
前記変異モジュールは、
前記ルーティングノードデプロイメント案中の第２所定数量の第１デプロイメント可能なルーティングノードのデプロイメント位置を、前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ルーティングノード位置に置換するための第１変異モジュール；又は、
前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードデプロイメント位置を選択し、各対の第２デプロイメント可能なルーティングノードデプロイメント位置間の最小コスト経路を計算し、前記最小コスト経路上の第３デプロイメント可能なルーティングノードデプロイメント位置を前記ルーティングノードデプロイメント案に追加するための第２変異モジュールを含む、装置。
【請求項９】
請求項1に記載のルーティングノード位置確定装置を含む端末装置。
【請求項１０】
ルーティングノード位置確定方法であって、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；
第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；及び
前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択することを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信技術分野に関し、特に、ルーティングノード位置確定方法、装置及び端末装置に関する。
【背景技術】
【０００２】
通信技術の進歩に伴い、無線センサネットワークは、迅速に発展しており、人々の生活に利便性をもたらしているとともに、人々のビジネスや生活のスタイルも変えている。
【０００３】
無線センサネットワークは、センサノード、ルーティングノード及びゲートウェイノードを含み、無線センサネットワークでは、ルーティングノードは、センサノードとゲートウェイノードとの情報交換のルートを構成し、ネットワークの重要な構成要素である。センサノードは、データ採集を完成した後に、データをゲートウェイノードに送る必要がある。センサノードとゲートウェイノードが直接通信することができない時に、ルーティングノードは、それらの間のデータを転送することができる。
【０００４】
実際のネットワークデプロイメント（deployment）では、ユーザは、具体的な応用ニーズや環境制限などに基づいて、センサノード及びゲートウェイノードの類型、数量及び位置を選択する。ネットワークのデプロイメント範囲がかなり大きい時に、センサノード及びゲートウェイノード間の距離が通信半径を超え、ネットワークを直接構成することが難しい。この時に、ネットワークに幾つかのルーティングノードをデプロイメントする必要がある。ルーティングノードは、センサノードとゲートウェイノードとを接続する役割を持ち、データ伝送の効率及び信頼性を決定する。また、ネットワーク中では、ルーティングノードの数量は、通常、かなり大きい割合を占め、即ち、ルーティングノードのハードウェアコスト、デプロイメントコスト及び保守コストは、ネットワークコストの重要な構成部分である。よって、ルーティングノード位置の選択は、ネットワークのパフォーマンス及びコストに大きな影響を与えている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の発明者は、次のようなことを発見した。即ち、今の無線センサネットワークのデプロイメントでは、作業員は、通常、経験又は特定の規則に従ってルーティングノード位置を選択する。例えば、よくある規則は、隣接ノード間の最大距離を制限し、ノード間に障害物がないように保証し、ノード位置が特定の幾何学図形を構成するなどを含む。しかしながら、このような方法は、ネットワークデプロイメントの信頼性を保証し、最適なデプロイメント効果を達成することができない。
【０００６】
本発明の実施例は、ルーティングノード位置確定方法、装置及び端末装置を提供し、これにより、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【課題を解決するための手段】
【０００７】
本発明の実施例の第１側面によれば、ルーティングノード位置確定装置が提供され、前記装置は、
初期化モジュールであって、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成するためのもの；
評価モジュールであって、第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であるもの；
処理モジュールであって、前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成するためのもの；及び
第１確定モジュールであって、前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択するためのものを含む。
【０００８】
本発明の実施例の第２側面によれば、端末装置が提供され、前記端末装置は、前述の第１側面に記載の装置を含む。
【０００９】
本発明の実施例の第３側面によれば、ルーティングノード位置確定方法が提供され、前記方法は、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；
第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；
前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択することを含む。
【００１０】
本発明の有益な効果は、本発明の実施例により、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【図面の簡単な説明】
【００１１】
【図１】実施例1中のルーティングノード位置確定装置を示す図である。
【図２】実施例1中の初期化モジュールの一例を示す図である。
【図３】実施例1中の初期化モジュールの一例のワーキングフローチャートである。
【図４】実施例1中で接続図に基づいて初期化ルーティングノードデプロイメント案集合を得ることを示す図である。
【図５】実施例1中で接続図に基づいて初期化ルーティングノードデプロイメント案集合を得ることを示す図である。
【図６】実施例1中の処理モジュールの一例を示す図である。
【図７】実施例1中の処理モジュールの一例のワーキングフローチャートである。
【図８】実施例1中の変異モジュールの一例のワーキングフローチャートである。
【図９】実施例1中の接続図に基づく変異処理の一例を示す図である。
【図１０】実施例1中の変異モジュールの一例のワーキングフローチャートである。
【図１１】実施例1中の接続図に基づく変異処理の一例を示す図である。
【図１２】実施例1中のルーティングノード位置確定装置のワーキングフローチャートである。
【図１３】実施例2中の端末装置を示す図である。
【図１４】実施例2中の端末装置のシステム構成図である。
【図１５】実施例3中のルーティングノード位置確定方法を示す図である。
【図１６】実施例3中のステップ1501の実施方式のフローチャートである。
【図１７】実施例3中のステップ1503の実施方式のフローチャートである。
【発明を実施するための形態】
【００１２】
以下、添付した図面を参照しながら、本発明を実施するための好適な形態を詳細に説明する。なお、以下に開示の実施形態は、例示に過ぎず、本発明を限定するものでない。
【００１３】
分かりやすくするために、以下、本発明の実施例に言及されている術語について説明する。遺伝的アルゴリズムは、生物の自然選択及び遺伝メカニズムに基づくランダム探索アルゴリズムであり、生物の進化過程をシミュレーションすることで最適探索を実現することができる。近年、遺伝的アルゴリズムは、無線ネットワークデプロイメント分野に幅広く応用されている。遺伝的アルゴリズムでは、解決しようとする問題の１つの解が個体と称され、複数の解が個体群（集合）と称される。本発明の実施例が解決しようとする問題は、ルーティングノードのデプロイメント案を確定することであるため、１つのルーティングノードデプロイメント案I=｛p1、p2、…、pi｝を遺伝的アルゴリズムの１つの個体と称し、そのうち、piは、１つのルーティングノードのデプロイメント位置であり、Iは、ネットワークデプロイメントが要する全てのルーティングノードのデプロイメント位置の集合である。
【００１４】
以下、図面を参照しながら、本発明の実施例について詳細に説明する。
【実施例１】
【００１５】
本発明の実施例は、ルーティングノード位置確定装置を提供する。図1は、前記装置を示す図である。図1に示すように、前記装置100は、初期化モジュール101、評価モジュール102、処理モジュール103、及び第１確定モジュール104を含む。そのうち、初期化モジュール101は、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；評価モジュール102は、第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；処理モジュール103は、前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；第１確定モジュール104は、前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択する。
【００１６】
本実施例では、初期化モジュール101は、第0世代ルーティングノードデプロイメント案集合を生成し、評価モジュール102は、第0（j=0）世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、処理モジュール103は、前記適応度に基づいて、第0世代ルーティングノードデプロイメント案集合に対して処理を行い、第1（j+1）世代ルーティングノードデプロイメント案集合を生成し、前記第1世代ルーティングノードデプロイメント案集合が所定条件を満足した場合、第１確定モジュール104は、前記第1世代ルーティングノードデプロイメント案集合から最終的なルーティングノードデプロイメント案を選択し、そうでない場合、第1世代ルーティングノードデプロイメント案集合に対して、評価モジュール102及び処理モジュール103は、類似した処理（j=1に相当）を行い、これに基づいて類推して、このような処理を、最終的なルーティングノードデプロイメント案を得るまで繰り返して行う。
【００１７】
本実施例の装置により、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【００１８】
以下、本実施例の前記ルーティングノード位置確定装置100の各構成部についてそれぞれ説明する。
【００１９】
本実施例では、初期化モジュール101は、第0世代ルーティングノードデプロイメント案集合を生成する前に、無線センサネットワークのネットワークデプロイメント情報を得る必要があり、該情報は、センサノード、ゲートウェイノード及びデプロイメント可能なルーティングノードの位置及びそれらの間の接続関係などを含み、そのうち、２つのノード間のリンク品質が予め設定された閾値よりも大きい時に、前記２つのノード間に接続関係が存在することを示し、前記リンク品質は、信号強度、パケットドロップ率（packet  drop  rate）などの指標により表されても良いが、本実施例は、これに限定されない。
【００２０】
１つの実施方式では、前記ネットワークデプロイメント情報は、接続図構造G=(V、E)により示されても良く、そのうち、Vは、頂点集合であり、ネットワーク中のセンサノードのデプロイメント位置の集合PS、ゲートウェイノードのデプロイメント位置の集合PG、及びルーティングノードのデプロイメント可能な位置の集合PRを含み、Eは、辺集合であり、接続関係が存在する２つのノードの集合を含み、E={(pi、pj)}であり、pi、pj∈Vであり、(pi、pj)は、pi及びpj間のリンク品質が予め設定された閾値よりも大きいこと、即ち、接続関係が存在することを示す。
【００２１】
図2は、前記初期化モジュール101の１つの実施方式を示す図である。図2に示すように、該実施方式では、前記初期化モジュール101は、計算モジュール201、第２確定モジュール202、及び更新モジュール203を含む。前記計算モジュール201は、リンク接続関係に基づいて、各センサノードから前記ゲートウェイノードまでの最小コスト経路を計算し、第２確定モジュール202は、全ての前記センサノードが前記最小コスト経路を有する時に、各最小コスト経路上のデプロイメント可能なルーティングノード位置集合を１つのルーティングノードデプロイメント案とし、更新モジュール203は、該１つのルーティングノードデプロイメント案中のデプロイメント可能なルーティングノードの位置を、前記リンク接続関係から除去して、更新されたリンク接続関係を生成し、これにより、前記初期化モジュール101は、更新されたリンク接続関係に基づいて、次の１つのルーティングノードデプロイメント案を生成する。
【００２２】
そのうち、最小コスト経路は、センサノードからゲートウェイノードまでのルーティングコストが最小のルーティング経路を表す。ルーティング経路は、複数のリンクからなり、そのうち、各リンクは、１つのルーティングコストを有し；ルーティング経路上の全てのリンクのルーティングコストの総和は、前記ルーティング経路のルーティングコストである。
【００２３】
本実施例では、前記第２確定モジュール202は、全てのセンサノードのうち、前記最小コスト経路を有しないセンサノードがある時に、その前に得られたルーティングノードデプロイメント案集合を、第0世代（初期）ルーティングノードデプロイメント案集合とする。
【００２４】
図3は、本実施例において初期化モジュール101が第0世代ルーティングノードデプロイメント案集合を生成するためのワーキングフローチャートである。図3に示すように、前記ワーキングフローは、次のようなステップを含む。
【００２５】
ステップ301：個体群を空集合Lと初期化し；
ステップ302：新しく追加された個体を空集合Iと初期化し；
ステップ303：センサノード集合PSから１つのノードpiを選択し；
ステップ304：計算モジュール201が、リンク接続関係に基づいて、piからゲートウェイノードまでの最小コスト経路Hを計算し；
ステップ305：Hが存在するかを判断し、判断結果がはいの場合、ステップ306を実行し、そうでない場合、操作を終了し；
ステップ306：第２確定モジュール202が、最小コスト経路H中のルーティングノード位置をIに追加し；
ステップ307：PSにはステップ304-306がまだ行われていないノードがあるかを判断し、判断結果がはいの場合、ステップ303に戻り、そうでない場合、ステップ308を実行し；
ステップ308：第２確定モジュール202が、得られた個体Iを個体群Lに追加し、且つ、更新モジュール203が、ステップ308で得られた集合I中のノードをPRから除去し、更新後の接続関係を取得し、そして、ステップ302に戻り、更新後のリンク接続関係に基づて、次の１つの個体Iを生成する。
【００２６】
ステップ304-306では、接続図Gに基づいて最小コスト経路を計算することができる。なお、具体的な計算方法は、従来技術を参照することができ、例えば、よくあるのは、Dijkstraアルゴリズム及びBellman-Fordアルゴリズムである。
【００２７】
図4及び図5は、本実施例において接続図に基づいて初期化することにより得られた第0世代ルーティングノードデプロイメント案集合を示す図である。図4及び5に示すように、S1及びS2は、センサノードであり、Wは、ゲートウェイノードであり、その他のノードA、B、C、D、E、F、H、Iは、ルーティングノードのデプロイメント可能な位置である。図4に示すように、ステップ302-308では、それぞれ、ノードS1及びS2からWまでの最小コスト経路を計算する（例えば、各辺のコストが同じであり、最小コスト経路が最短路径に相当するとする）。例えば、S1からWまでの最小コスト経路は、S1-B-E-Wであり、S2からWまでの最小コスト経路は、S2-I-Wである。そして、最小コスト経路上のノードB、E、Iを個体I1に追加し、個体I1を個体群Lに追加し、その後、ステップ309を行って、ノードB、E、IをPRから除去し、更新後の接続図を得る。図5に示すように、図5に示す更新後の接続図において、上述のステップ302-308を繰り返し、新しい個体I2=｛A、C、D、F、H｝を取得し、そして、新しい個体I2を個体群Lに追加し、個体群L=｛I1、I2｝を取得する。I2中のノードを図5から除去した後に、S1及びS2は、ゲートウェイノードまでの最小コスト経路を有しないので、個体群初期化操作を終了し、個体群L=｛I1、I2｝を第0世代ルーティングノードデプロイメント案集合とする。
【００２８】
本実施例では、評価モジュール102は、第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数を、前記ルーティングノードデプロイメント案の適応度として計算し、これにより、センサノードのルーティング経路コストが最小であることを保証し、また、ルーティングノードの数量を最小化することができる。
【００２９】
１つの実施方式では、評価モジュール102は、前記各ルーティングノードデプロイメント案中のルーティングノード数量、及び各センサノードからゲートウェイノードまでの第１最小コスト経路と、各センサノードから前記ゲートウェイノードまでの第２最小コスト経路とのルーティングコストの差に基づいて、前記各ルーティングノードデプロイメント案の適応度を計算し、そのうち、前記第１最小コスト経路は、前記ルーティングノードデプロイメント案中のルーティングノード位置範囲内のルーティングノードを通過し、前記第２最小コスト経路は、全てのデプロイメント可能なルーティングノード範囲内のルーティングノードを通過する。
【００３０】
そのうち、評価モジュール102は、公式（1）により、前記各ルーティングノードデプロイメント案の適応度Fを計算することができる。
【数１】
2018056989.tif 000003
【００３１】
そのうち、｜I｜は、該ルーティングノードデプロイメント案中のルーティングノードの数量であり、｜PS｜は、ネットワーク中のセンサノードの個数であり、liは、前記第１最小コスト経路のルーティングコストであり、即ち、I中のルーティングノード位置を通過する、センサノードpiからゲートウェイノードまでの最小コスト経路のルーティングコストであり、li′は、前記第２最小コスト経路のルーティングコストであり、即ち、全てのデプロイメント可能なルーティングノード位置を通過する、センサノードpiからゲートウェイノードまでの最小コスト経路のルーティングコストであり、λは、ルーティング経路長さとルーティングノード数量との関係を調整するために用いられ、実際の状況に応じて確定されても良いが、本実施例は、これに限定されず、また、iは、1からSまでの間の整数である。
【００３２】
以下、図4及び図5を例として、如何にルーティングノードデプロイメント案の適応度を計算するかを説明する。λ=1とする。図4に示すように、センサノードは、PS={S1、S2}であり、全てのルーティングノードのデプロイメント可能な位置A、B、C、D、E、F、H、Iを通過する、S1からWまでの最小コスト経路は、S1-B-E-Wであり、S2からWまでの最小コスト経路は、S2-I-Wであり、また、上述のステップ301-309で得られた１つのルーティングノードデプロイメント案I1={B、E、I}により、I1中のルーティングノード位置を通過する、S1からWまでの最小コスト経路は、S1-B-E-Wであり、S2からWまでの最小コスト経路は、S2-I-Wである。よって、公式（1）中では、｜I｜=3、｜PS｜=2、l1′=l1=2、l2′=l2=1であり、個体I1の適応度は、F=3である。図5に示すように、上述のステップ301-309で得られた１つのルーティングノードデプロイメント案は、I2={A、C、D、F、H}であり、I2中のルーティングノード位置を通過する、S1からWまでの最小コスト経路は、S1-C-F-H-Wであり、S2からWまでの最小コスト経路は、S2-D-A-S1-C-F-H-Wである。よって、公式（1）では、｜I｜=5、｜PS｜=2、l1′=2、l2′=1、l1=3、l2=6であり、個体I2の適応度は、F=8である。
【００３３】
本実施例では、処理モジュール103は、評価モジュール102が計算した適応度に基づいて、第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し、そのうち、遺伝的アルゴリズムを用いて第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成することができる。遺伝的アルゴリズムは、多くの具体的な実施方式があり、例えば、（μ、λ）方法及び（μ＋λ）方法があるが、本実施例は、これに限定されない。遺伝的アルゴリズムは、通常、選択、ペアリング・交叉、及び変異（突然変異とも称される）処理を含み、そのうち、選択処理は、適応度に基づいて、前の１つの世代の個体群から一部を次の世代の個体群として選択し、ペアリング処理は、１つの個体群から一部の個体対（ペア）を選択し、交叉処理は、選択された個体対の情報に対して交叉交換を行い、新しい個体を生成し、変異処理は、一部の個体の情報に対して変更を行い、そのうち、選択、ペアリング・交叉、及び変異処理は、従来技術を採用しても良いが、本実施例は、これに限定されない。
【００３４】
処理モジュール103は、第j世代ルーティングノードデプロイメント案集合を処理した後に、第j+1世代ルーティングノードデプロイメント案集合を生成し、前記j+1代ルーティングノードデプロイメント案集合が所定条件を満足したかを判断する。１つの実施方式では、前記所定条件は、j+1が第１閾値Nに等しいことであり、そのうち、Nは、1以上の整数であるが、本実施例は、これに限定されない。前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足した時に、評価モジュール102は、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算することができ、且つ第１確定モジュール104は、第j+1世代ルーティングノードデプロイメント案集合中の適応度が最小のルーティングノードデプロイメント案を、最終的なルーティングノードデプロイメント案とすることができる。なお、本実施例は、これに限定されない。前記第１確定モジュール104は、さらに、他の原則を用いて、ルーティングノードデプロイメント案集合から最終的なルーティングノードデプロイメント案を選択しても良い。前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足しない時に、評価モジュール102は、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算することができ、処理モジュール103は、評価モジュール102が計算した第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度に基づいて、前記第j+1世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+2世代ルーティングノードデプロイメント案集合を生成し、また、上述の処理を、前記所定条件を満足したルーティングノードデプロイメント案集合を生成できるまで繰り返して行い、これにより、第１確定モジュール104は、前記所定条件を満足したルーティングノードデプロイメント案集合から最終的なルーティングノードデプロイメント案を選択することができる。
【００３５】
図6は、本実施例中の処理モジュール103の１つの実施方式を示す図である。図6に示すように、前記処理モジュールは、選択モジュール601、ペアリング・交叉モジュール602、及び変異モジュール603を含み、選択モジュール601は、第j世代ルーティングノードデプロイメント案集合から、適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択し、第１ルーティングノードデプロイメント案集合を取得し；ペアリング・交叉モジュール602は、前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して、ペアリング・交叉処理を行い；変異モジュール603は、ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行い、前記第j+1世代ルーティングノードデプロイメント案集合を取得する。
【００３６】
本実施例では、さらに、前記変異モジュール603を改良しており、１つの実施方式では、前記変異モジュール603は、第１変異モジュール（図示せず）を含んでも良く、それは、前記ルーティングノードデプロイメント案中の第２所定数量個の第１デプロイメント可能なルーティングノードのデプロイメント位置を、前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ルーティングノード位置に取り替え、もう１つの実施方式では、前記変異モジュール603は、第２変異モジュール（図示せず）を含んでも良く、それは、前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードのデプロイメント位置を選択し、各対の第２デプロイメント可能なルーティングノードのデプロイメント位置間の最小コスト経路を計算し、前記最小コスト経路上の第３デプロイメント可能なルーティングノードのデプロイメント位置を前記ルーティングノードデプロイメント案に追加する。
【００３７】
本実施例では、前記処理モジュール103は、さらに、判断モジュール（図示せず）を含んでも良く、それは、前記j+1世代ルーティングノードデプロイメント案集合が所定条件を満足したかを判断するために用いられ、判断結果がはいの場合、第１確定モジュール104は、所定条件を満足したルーティングノードデプロイメント案集合から、最終的なルーティングノードデプロイメント案を確定し、判断結果がいいえの場合、評価モジュール102及び処理モジュール103は、前記第j+1世代ルーティングノードデプロイメント案集合に対して反復処理を行う。以下、処理モジュール103の具体的なワーキングフローを詳しく説明する。
【００３８】
図7は、前記処理モジュール103が、ある世代のルーティングノードデプロイメント案集合に対して処理を行う具体的な処理方法のフローチャートである。図7に示すように、このワーキングフローは、次のようなステップを含む。
【００３９】
ステップ701：選択モジュール601が、第j世代ルーティングノードデプロイメント案集合から、適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択し、第１ルーティングノードデプロイメント案集合を取得し；
ステップ702：ペアリング・交叉モジュール602が前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対してペアリング・交叉処理を行い；
ステップ703：変異モジュール603が、ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行い、前記第j+1世代ルーティングノードデプロイメント案集合を取得する。
【００４０】
本実施例では、ステップ701は、遺伝的アルゴリズム中の選択過程に相当し、ステップ701では、次のような方式を採用して前記第１ルーティングノードデプロイメント案集合を得ても良く、例えば、第j世代ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案を、適応度の大から小への順序に従って並べ替え、第j世代ルーティングノードデプロイメント案集合から、適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択しても良く、そのうち、前記第１所定数量は、ニーズに応じて設定されても良い。
【００４１】
本実施例では、ステップ702は、遺伝的アルゴリズム中のペアリング・交叉過程に相当し、ステップ702では、前記第１ルーティングノードデプロイメント案集合Aにトータルで第１所定数量M個のデプロイメント方案があり、各デプロイメント案がA(m)と表され、m=1、2、…、Mであるとし、前記第１ルーティングノードデプロイメント案集合から、第４所定数量P対のデプロイメント案を選択し、前記各対のデプロイメント案中の２つのデプロイメント方案A（ｓ）及びA（ｔ）の一部のルーティングノード位置を交換し、２つの新しい方案A（ｓ）′及びA（ｔ）′を取得し、これによる、新しい案の集合A′を得ることができ、そのうち、s及びtの値は、1〜Mである。
【００４２】
例えば、選択された１対のデプロイメント案は、I1={B、E、I}、I2={A、C、D、F、H}であり、その後、I1中の一部のルーティングノード位置とI2中の一部のルーティングノード位置を交換し、例えば、I1中のノードBとI2中のノードAを交換し、新しい１対のデプロイメント案として、I1’={A、E、I}、I2’={B、C、D、F、H}を取得し、又は、I1中のノードB、IとI2中のノードD、Fを交換し、新しい１対のデプロイメント案として、I1’={D、E、F}、I2’={A、C、B、I、H}を取得することができる。
【００４３】
そのうち、１対のA（ｓ）とA（ｔ）の交換が完成した後に、上述の同じ方法で、その他のP-1対のデプロイメント案の交換を行う。なお、交換プロセスは、上述のプロセスと同じであるため、ここでは、その詳しい説明を省略する。
【００４４】
本実施例では、ステップ703は、遺伝的アルゴリズム中の変異過程に相当し、ステップ703では、前記新しい案の集合A′から所定数量のデプロイメント案を選択し、前記所定数量のデプロイメント案から所定位置を選択し、それを現在と異なるノードに変更し、且つ変異後のノードは、前記デプロイメント案中の他のノードの位置と重複（overlap）しない。
【００４５】
１つの実施方式では、変異時に、前記ルーティングノードデプロイメント案中の第２所定数量の第１デプロイメント可能なルーティングノードのデプロイメント位置を、前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ルーティングノード位置に取り替えても良い。
【００４６】
図8は、前記変異処理の実施方式のフローチャートである。図8に示すように、前記ワーキングフローは、次のステップを含む。
【００４７】
ステップ801：変異を行う必要があるルーティングノードデプロイメント案I=｛p1、p2、…、pi｝を選択し；
ステップ802：I中の第２所定数量n個のデプロイメント位置piに対して、次のステップ803及び804中の操作を行い；
そのうち、前記第２所定数量nは、ニーズに応じて確定されても良いが、本実施例は、これに限定されない。
【００４８】
ステップ803：１つのノードpiの隣接ルーティングノードpjを選択し；
そのうち、接続図Gに基づいて、ノードpiの隣接ノードから１つの隣接ノードpjをランダムに選択しても良く；
ステップ804：ルーティングノードデプロイメント案中のpiをpjに置換し；
ステップ805：I中のn個のデプロイメント位置piについて、ステップ803及び804中の操作を完成する。
【００４９】
図9は、変異処理の１つの実施方式を示す図である。図9に示すように、ルーティングノードデプロイメント案I=｛B、E、I｝であるとし、前記第２所定数量n=3であるとし、そして、全てのルーティングノードデプロイメント位置に対してステップ803及び804を行い、例えば、ノードBについて、その隣接ノードが｛S1、A、C｝であり、ランダムに１つのルーティングノード例えばAを選択して、I中のノードBを取り替え、ノードEについて、その隣接ノードが｛B、D、H、I｝であり、ランダムに１つのルーティングノードDを選択して、I中のノードEを取り替え、また、ノードIについて、その隣接ノードが｛S2、D、E、H｝であり、ランダムに１つのルーティングノードEを選択して、I中のノードIを取り替え、これにより、変異後の新しいルーティングノードデプロイメント案I′=｛A、D、E｝を得ることができる。
【００５０】
もう１つの実施方式では、変異時に、前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードのデプロイメント位置を選択し、各対の第２デプロイメント可能なルーティングノードのデプロイメント位置間の最小コスト経路を計算し、該最小コスト経路上の第３デプロイメント可能なルーティングノードのデプロイメント位置を前記ルーティングノードデプロイメント案に追加しても良い。
【００５１】
図10は、この変異処理の実施方式のフローチャートである。図10に示すように、このワーキングフローは、次のようなステップを含む。
【００５２】
ステップ1001：変異を行う必要があるルーティングノードデプロイメント案I=｛p1、p2、…、pi｝を選択し；
ステップ1002：I中の第３所定数量q対のデプロイメント位置（pi、pj）に対して、次のステップ1003及び1004中の操作を行い；
そのうち、前記第３所定数量q対は、ニーズに応じて確定されても良いが、本実施例は、これに限定されない。
【００５３】
ステップ1003：piからpjまでの最小コスト経路Hを計算し；
そのうち、接続図Gに基づいて、piからpjまでの最小コスト経路Hを計算しても良く、その具体的な実施方式は、従来技術を参照することができるので、ここでは、その詳しい説明を省略する。
【００５４】
ステップ1004：最小コスト経路H上のルーティングノードデプロイメント位置をIに追加し；
ステップ1005：I中のq対のデプロイメント位置（pi、pj）について、ステップ1003及び1004中の操作を完成する。
【００５５】
図11は、変異処理の１つの実施方法を示す図である。図11に示すように、ルーティングノードデプロイメント案I=｛C、E、F、H、J｝であるとし、前記第３所定数量q=1であるとし、そして、Iから1対のデプロイメント位置を選択して、ステップ1003及び1004を行い、例えば、選択された１対のデプロイメント位置が｛C、E｝であり、接続図G（各辺のコストが同じであるとする）に基づいて、CからEまでの最小コスト経路をC-B-Eとして計算し、最小コスト経路上のルーティングノード位置Bを原ルーティングノードデプロイメント案Iに追加し、これにより、変異後の新しいルーティングノードデプロイメント案I’=｛B、C、E、F、H、J｝を得ることができる。
【００５６】
上述の変異処理の具体的な実施方式は、単独で実施されても良く、組み合わせて実施されても良いが、本実施例は、これに限定されない、且つ、本実施例は、上述の変異処理の実施方式にも限定されない。
【００５７】
図12は、本実施例の装置100がルーティングノード位置を確定する一例のフローチャートである。図12に示すように、前記ワーキングフローは、次のようなステップを含む。
【００５８】
ステップ1201：初期化モジュール101が、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、初期ルーティングノードデプロイメント案集合を生成し、現在の初期デプロイメント方案集合を第j世代（j=0）とし；
ステップ1202：評価モジュール102が、第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し；
ステップ1203：処理モジュール103が、前記適応度に基づいて、第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；
ステップ1204：第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足したかを判断し、判断結果がはいの場合、ステップ1205を行い、そうでない場合、j=j+1とし、そして、ステップ1202を実行し；
ステップ1205：前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択する。
【００５９】
そのうち、ステップ1201-1205の具体的な実施細部について、上述の記載を参照することができるので、ここでは、その詳しい説明を省略する。
【００６０】
本実施例の装置により、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【実施例２】
【００６１】
本発明の実施例は、端末装置を提供し、前記端末装置は、実施例1に記載の無線ネットワークデプロイメント用の装置を含む。
【００６２】
図13は、前記端末装置を示す図である。図13に示すように、前記端末装置1300は、ルーティングノード位置確定装置100を含み、前記装置100は、次のように構成され、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択する。なお、実施例1で前記ルーティングノード位置確定装置100について詳細に説明したので、その内容は、ここに合併され、ここでは、その詳しい説明を省略する。
【００６３】
図14は、本実施例の端末装置のシステム構成図である。図14に示すように、前記端末装置1400は、中央処理装置1401及び記憶器1402を含んでも良く、記憶器1402は、中央処理装置1401に接続される。なお、該図は、例示に過ぎず、さらに、その他の類型の構造を以て該構造に対して補充又は代替を行うことで、電気通信機能やその他の機能を実現することもできる。
【００６４】
１つの実施方式では、実施例1に記載のルーティングノード位置確定装置100の機能は、中央処理装置1401に集積することができる。例えば、前記中央処理器1401は、次のように構成されても良く、即ち、ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択する。
【００６５】
もう１つの実施方式では、実施例1に記載のルーティングノード位置確定装置100は、中央処理装置1401と別々で構成されても良く、例えば、前記装置100を、中央処理装置器1401に接続されるチップとして構成し、中央処理装置1401の制御により、ルーティングノード位置確定装置100の機能を実現しても良い。
【００６６】
図14に示すように、前記端末装置1400は、さらに、通信モジュール1403、入力ユニット1404、音声処理器1405、表示器1406、電源1407を含んでも良い。なお、端末装置1400は、必ずしも図14中のの全ての部品を含む必要がない。また、端末装置1400は、さらに、図14に無い部品を含んでも良く、これについては、従来技術を参照することができる。
【００６７】
図14に示すように、中央処理装置1401は、制御器又は操作コントローラと称される場合があり、マイクロプロセッサ又は他の処理装置及び/又は論理装置を含んでも良く、また、前記中央処理器1401は、入力を受信し、端末装置1400の各部品の操作を制御することができる。
【００６８】
そのうち、記憶器1402は、例えば、バッファ、フレッシュメモリ、HDD、移動可能な媒体、揮発性記憶器、不揮発性記憶儲器又はその他の適切な装置のうちの一つ又は複数であっても良い。上述のネットワークデプロイメント情報を記憶することができ、また、さらに情報処理に関するプログラムを記憶することもできる。また、中央処理装置1401は、記憶器1402に記憶された前記プログラムを、情報の記憶や処理などを実現するために実行しても良い。なお、その他の部品の機能は、従来に類似したので、ここでは、その詳しい説明を省略する。また、端末装置1400の各部品は、専用ハードウェア、ファームウェア、ソフトウェア又は組み合わせにより実現されてもよく、これらは、すべて、本発明の範囲に属する。
【００６９】
本実施例の端末装置により、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【実施例３】
【００７０】
本発明の実施例は、ルーティングノード位置確定方法を提供し、該方法が問題を解決する原理は、実施例1の装置に類似したので、その具体的な実施は、実施例1の装置の実施を参照することができ、内容が同じである重複説明は、省略される。
【００７１】
図15は、本実施例のルーティングノード位置確定方法の１つの実施方式のフローチャートである。図15に示すように、前記方法は、次のようなステップを含む。
【００７２】
ステップ1501：ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；
ステップ1502：第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；
ステップ1503：前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；
ステップ1504：前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択する。
【００７３】
本実施例では、ステップ1502では、前記各ルーティングノードデプロイメント案中のルーティングノード数量、及び、各センサノードからゲートウェイノードまでの第１最小コスト経路と、各センサノードから前記ゲートウェイノードまでの第２最小コスト経路とのルーティングコストの差に基づいて、前記各ルーティングノードデプロイメント案の適応度を計算することができる。
【００７４】
そのうち、前記第１最小コスト経路は、前記ルーティングノードデプロイメント案中のルーティングノード位置範囲内のルーティングノードを通過し、前記第２最小コスト経路は、全てのデプロイメント可能なルーティングノード範囲内のルーティングノードを通過する。
【００７５】
１つの実施方式では、実施例1中の公式（1）を用いて、前記各ルーティングノードデプロイメント案の適応度Fを計算することができる。なお、その具体的な計算方法は、実施例1を参照することができ、ここでは、その詳しい説明を省略する。
【００７６】
本実施例では、前記所定条件は、j+1が第１閾値Nに等しいことであり、そのうち、Nは、1以上の整数であり、前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足した時に、ステップ1502に戻り、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、そして、ステップ1504では、前記適応度が最小のルーティングノードデプロイメント案を、最終的なルーティングノードデプロイメント案と確定する。
【００７７】
本実施例では、前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足しない時に、ステップ1502に戻り、第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、そして、ステップ1503では、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度に基づいて、前記第j+1世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+2世代ルーティングノードデプロイメント案集合を生成する。
【００７８】
図16は、本実施例のステップ1501の一実施方式のフローチャートである。図16に示すように、前記方法は、次のようなステップを含む。
【００７９】
ステップ1601：リンク接続関係に基づいて、各センサノードから前記ゲートウェイノードまでの最小コスト経路を計算し；
ステップ1602：全ての前記センサノードが前記最小コスト経路を有する時に、各最小コスト経路上のデプロイメント可能なルーティングノード位置集合を、１つのルーティングノードデプロイメント案とし；
ステップ1603：前記１つのルーティングノードデプロイメント案中のデプロイメント可能なルーティングノードの位置を前記リンク接続関係から除去し、更新後のリンク接続関係を生成し、これにより、更新後のリンク接続関係に基づいて、次の１つのルーティングノードデプロイメント案を生成する。
【００８０】
そのうち、ステップ1602では、全てのセンサノードのうち、前記最小コスト経路を有しないセンサノードがある時に、その前に得られたルーティングノードデプロイメント案集合を第0世代ルーティングノードデプロイメント案集合とする。
【００８１】
図17は、本実施例のステップ1503の一実施方式のフローチャートである。図17に示すように、前記方法は、
ステップ1701：第j世代ルーティングノードデプロイメント案集合から、適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択し、第１ルーティングノードデプロイメント案集合を取得し；
ステップ1702：前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対してペアリング・交叉処理を行い；
ステップ1703：ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行い、前記第j+1世代ルーティングノードデプロイメント案集合を取得する。
【００８２】
１つの実施方式では、ステップ1703では、前記ルーティングノードデプロイメント案中の第２所定数量の第１デプロイメント可能なルーティングノードのデプロイメント位置を、前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ノード位置に置換する。
【００８３】
もう１つの実施方式では、ステップ1703では、前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードのデプロイメント位置を選択し；各対の第２デプロイメント可能なルーティングノードのデプロイメント位置間の最小コスト経路を計算し；前記最小コスト経路上の第３デプロイメント可能なルーティングノードのデプロイメント位置を前記ルーティングノードデプロイメント案に追加しても良い。
【００８４】
本実施例の方法により、ルーティングノード位置確定時に、最適ルーティングノード数量だけでなく、最適ルーティング経路も考慮したので、ネットワークデータ伝送パフォーマンスを保証でき、且つルーティングノード数量が最小のルーティングノードデプロイメント案を得ることができる。
【００８５】
本発明の実施例は、さらに、コンピュータ可読プログラムを提供し、そのうち、端末装置中で前記プログラムを実行する時に、前記プログラムは、前記コンピュータに、実施例3に記載の方法を実行させる。
【００８６】
本発明の実施例は、さらに、コンピュータ可読プログラムを記憶した記憶媒体を提供し、そのうち、前記コンピュータ可読プログラムは、端末装置中で実行される時に、コンピュータに、実施例3に記載の方法を実行させる。
【００８７】
本発明の実施例による装置及び方法は、ソフトウェアにより実現されても良く、ハードェアにより実現されてもよく、ハードェア及びソフトウェアの組み合わせにより実現されても良い。また、本発明は、このようなコンピュータ可読プログラムにも関し、即ち、前記プログラムは、ロジック部品により実行される時に、前記ロジック部品に、上述の装置又は構成要素を実現させることができ、又は、前記ロジック部品に、上述の方法又はそのステップを実現させることができる。さらに、本発明は、上述のプログラムを記憶するための記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、フレッシュメモリなどにも関する。
【００８８】
また、以上の複数の実施例に関し、さらに、次のような付記も開示する。
【００８９】
（付記1）
ルーティングノード位置確定装置であって、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成するための初期化モジュール；
第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算するための評価モジュールであって、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数である、評価モジュール；
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成するための処理モジュール；及び
前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択するための第１確定モジュールを含む、装置。
【００９０】
（付記2）
付記1に記載の装置であって、
前記評価モジュールは、前記各ルーティングノードデプロイメント案中のルーティングノード数量、及び、各センサノードからゲートウェイノードまでの第１最小コスト経路と、各センサノードから前記ゲートウェイノードまでの第２最小コスト経路とのルーティングコストの差に基づいて、前記各ルーティングノードデプロイメント案の適応度を計算し、
そのうち、前記第１最小コスト経路は、前記ルーティングノードデプロイメント案中のルーティングノード位置範囲内のルーティングノードを通過し、前記第２最小コスト経路は、全てのデプロイメント可能なルーティングノード範囲内のルーティングノードを通過する、装置。
【００９１】
（付記3）
付記2に記載の装置であって、
前記評価モジュールは、
【数２】
2018056989.tif 000004
を用いて、前記各ルーティングノードデプロイメント案の適応度Fを計算し、
そのうち、｜I|は、前記ルーティングノードデプロイメント案中のルーティングノード数量であり、｜Ps|は、ネットワーク中のセンサノードの個数であり、liは、前記第１最小コスト経路のルーティングコストであり、li′は、前記第２最小コスト経路のルーティングコストであり、λは、ルーティング経路長さとルーティングノード数量の関係を調整するために用いられ、iは、1乃至S間の整数である、装置。
【００９２】
（付記4）
付記1に記載の装置であって、
前記所定条件は、j+1が第１閾値Nに等しいことであり、そのうち、Nは、1以上の整数であり、前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足した時に、前記評価モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し；
前記第１確定モジュールは、前記適応度が最小のルーティングノードデプロイメント案を、最終的なルーティングノードデプロイメント案と確定し;
前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足しない時に、前記評価モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記処理モジュールは、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度に基づいて、前記第j+1世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+2世代ルーティングノードデプロイメント案集合を生成する、装置。
【００９３】
（付記5）
付記1に記載の装置であって、
前記初期化モジュールは、
リンク接続関係に基づいて、各センサノードから前記ゲートウェイノードまでの最小コスト経路を計算するための計算モジュール；
全ての前記センサノードが前記最小コスト経路を有する時に、各最小コスト経路上のデプロイメント可能なルーティングノード位置集合を、１つのルーティングノードデプロイメント案とするための第２確定モジュール；及び
前記１つのルーティングノードデプロイメント案中のデプロイメント可能なルーティングノードの位置を前記リンク接続関係から除去し、更新後のリンク接続関係を生成し、これにより、前記初期化モジュールは、更新後のリンク接続関係に基づいて、次の１つのルーティングノードデプロイメント案を生成するための更新モジュールを含む、装置。
【００９４】
（付記6）
付記5に記載の装置であって、
前記第２確定モジュールは、全てのセンサノードのうち、前記最小コスト経路を有しないセンサノードがある時に、その前に得られたルーティングノードデプロイメント案集合を第0世代ルーティングノードデプロイメント案集合とする、装置。
【００９５】
（付記7）
付記1に記載の装置であって、
前記処理モジュールは、
第j世代ルーティングノードデプロイメント案集合から適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択し、第１ルーティングノードデプロイメント案集合を取得するための選択モジュール；
前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対してペアリング・交叉処理を行うためのペアリング・交叉モジュール；
ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行い、前記第j+1世代ルーティングノードデプロイメント案集合を得るための変異モジュールを含む、装置。
【００９６】
（付記8）
付記7に記載の装置であって、
前記変異モジュールは、
前記ルーティングノードデプロイメント案中の第２所定数量の第１デプロイメント可能なルーティングノードのデプロイメント位置を前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ルーティングノード位置に取り替えるための第１変異モジュール；又は、
前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードデプロイメント位置を選択し、各対の第２デプロイメント可能なルーティングノードのデプロイメント位置間の最小コスト経路を計算し、前記最小コスト経路上の第３デプロイメント可能なルーティングノードデプロイメント位置を前記ルーティングノードデプロイメント案に追加するための第２変異モジュールを含む、装置。
【００９７】
（付記9）
付記1に記載のルーティングノード位置確定装置を含む端末装置。
【００９８】
（付記10）
ルーティングノード位置確定方法であって、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成し；
第j世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記適応度は、各ルーティングノードデプロイメント案の最小コスト経路とルーティングノード数量の関係関数であり、jは、0以上の整数であり；
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成し；及び
前記第j+1世代ルーティングノードデプロイメント案集合が所定条件を満足した時に、前記所定条件を満足したルーティングノードデプロイメント案集合からルーティングノードデプロイメント案を選択することを含む、方法。
【００９９】
（付記11）
付記10に記載の方法であって、
前記各ルーティングノードデプロイメント案中のルーティングノード数量、及び、各センサノードからゲートウェイノードまでの第１最小コスト経路と、各センサノードから前記ゲートウェイノードまでの第２最小コスト経路とのルーティングコストの差に基づいて、前記各ルーティングノードデプロイメント案の適応度を計算し；
そのうち、前記第１最小コスト経路は、前記ルーティングノードデプロイメント案中のルーティングノード位置範囲内のルーティングノードを通過し、前記第２最小コスト経路は、全てのデプロイメント可能なルーティングノード範囲内のルーティングノードを通過する、方法。
【０１００】
（付記12）
付記11に記載の方法であって、
【数３】
2018056989.tif 000005
を用いて、前記各ルーティングノードデプロイメント案の適応度Fを計算し、
そのうち、｜I|は、前記ルーティングノードデプロイメント案中のルーティングノードの数量であり、｜PS|は、ネットワーク中のセンサノードの個数であり、liは、前記第１最小コスト経路のルーティングコストであり、li′は、前記第２最小コスト経路のルーティングコストであり、λは、ルーティング経路長さとルーティングノード数量の関係を調整するために用いられ、iは、1からSまでの間の整数である、方法。
【０１０１】
（付記13）
付記10に記載の方法であって、
前記所定条件は、j+1が第１閾値Nに等しいことであり、そのうち、Nは、1以上の整数であり、前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足した時に、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、そして、前記適応度が最小のルーティングノードデプロイメント案を最終的なルーティングノードデプロイメント案と確定する、方法。
【０１０２】
（付記14）
付記10に記載の方法であって、
ネットワーク中のセンサノード、ゲートウェイノード及びデプロイメント可能なルーティングノード間のリンク接続関係に基づいて、第0世代ルーティングノードデプロイメント案集合を生成することは、
リンク接続関係に基づいて、各センサノードから前記ゲートウェイノードまでの最小コスト経路を計算し；
全ての前記センサノードが前記最小コスト経路を有する時に、各最小コスト経路上のデプロイメント可能なルーティングノード位置集合を１つのルーティングノードデプロイメント案とし；
前記１つのルーティングノードデプロイメント案中のデプロイメント可能なルーティングノードの位置を前記リンク接続関係から除去し、更新後のリンク接続関係を生成し、これにより、更新後のリンク接続関係に基づいて、次の１つのルーティングノードデプロイメント案を生成し;
前記第j+1世代ルーティングノードデプロイメント案集合が前記所定条件を満足しない時に、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度を計算し、前記第j+1世代ルーティングノードデプロイメント案集合中の各ルーティングノードデプロイメント案の適応度に基づいて、前記第j+1世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+2世代ルーティングノードデプロイメント案集合を生成することを含む、方法。
【０１０３】
（付記15）
付記14に記載の方法であって、
全てのセンサノードのうち、前記最小コスト経路を有しなセンサノードがある時に、その前に得られたルーティングノードデプロイメント案集合を第0世代ルーティングノードデプロイメント案集合とする、方法。
【０１０４】
（付記16）
付記10に記載の方法であって、
前記適応度に基づいて、前記第j世代ルーティングノードデプロイメント案集合に対して処理を行い、第j+1世代ルーティングノードデプロイメント案集合を生成することは、
第j世代ルーティングノードデプロイメント案集合から適応度が比較的高い第１所定数量のルーティングノードデプロイメント案を選択し、第１ルーティングノードデプロイメント案集合を取得し；
前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対してペアリング・交叉処理を行い；及び
ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行い、前記第j+1世代ルーティングノードデプロイメント案集合を得ることを含む、方法。
【０１０５】
（付記17）
付記16に記載の方法であって、
ペアリング・交叉処理後の前記第１ルーティングノードデプロイメント案集合中のルーティングノードデプロイメント案に対して変異処理を行うことは、
前記ルーティングノードデプロイメント案中の第２所定数量の第１デプロイメント可能なルーティングノードのデプロイメント位置を前記第１デプロイメント可能なルーティングノードのデプロイメント位置の１つの隣接ルーティングノード位置に取り替えること；又は、
前記ルーティングノードデプロイメント案中の第３所定数量対の第２デプロイメント可能なルーティングノードデプロイメント位置を選択し、各対の第２デプロイメント可能なルーティングノードデプロイメント位置間の最小コスト経路を計算し、前記最小コスト経路上の第３デプロイメント可能なルーティングノードデプロイメント位置を前記ルーティングノードデプロイメント案に追加することを含む、方法。
【０１０６】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
2018056989.tif 000007
【図２】
2018056989.tif 000008
【図３】
2018056989.tif 000009
【図４】
2018056989.tif 000010
【図５】
2018056989.tif 000011
【図６】
2018056989.tif 000012
【図７】
2018056989.tif 000013
【図８】
2018056989.tif 000014
【図９】
2018056989.tif 000015
【図１０】
2018056989.tif 000016
【図１１】
2018056989.tif 000017
【図１２】
2018056989.tif 000018
【図１３】
2018056989.tif 000019
【図１４】
2018056989.tif 000020
【図１５】
2018056989.tif 000021
【図１６】
2018056989.tif 000022
【図１７】
2018056989.tif 000023