11

私はN個のノードを持つ（理論上の）ネットワークを持っており、それぞれが独自の固定位置を持っています。各ノードはサイクルごとに1つのメッセージを送信します。このメッセージは、直接または他のノードを介してルートに到達する必要があります。

ノードAからノードBにメッセージを送信するためのエネルギーコストは、それらの間の距離の2乗です。

課題は、これらのノードをツリー形式でリンクして、最もエネルギー効率の高いネットワークを作成する方法です。

たとえば、これらのノードをリンクする2つの可能な方法がありますが、左側の方がエネルギー効率が高くなっています。

私は問題を解決するために遺伝的アルゴリズムに取り組んでいますが、誰かが他のアイデアを持っているか、または関連するオープンソースコードを知っているかどうか疑問に思いました。

編集：私が言及するのを忘れたネットワークの別の側面は、各ノードがバッテリー駆動であるということです。したがって、同じノードを介してルーティングされるメッセージが多すぎると、そのノードのバッテリーが使い果たされ、ネットワークに障害が発生します。ネットワークのエネルギー効率は、ノードのバッテリーがなくなる前に、各ノードからルートに正常に送信できるメッセージの数によって測定されます。

編集＃2：質問の元のテキストが欠落していることをお詫びします。そのため、以前の回答のいくつかは私が探しているものではありませんが、MSTアルゴリズムに精通していなかったので、それらについて教えてくれてありがとう。

物事をより明確にすることを期待して、これを追加させてください：

内部ノードを含め、すべてのノードがサイクルごとに1つのメッセージを送信します。内部ノードは、受信したメッセージを中継する役割も果たします。これは、彼らが彼ら自身の追加のメッセージを送っていた場合、彼らのバッテリーの負担を増します。目的は、ノードのバッテリーがなくなる前に達成されるサイクルの量を最大化することです。

4

8 に答える 8

6

完全なグラフを作成し、各ノードでダイクストラの最短パスアルゴリズムを使用して、そのノードの最小コストのルートを見つけることができると思います。これらのパスの結合は、最小コストツリーを形成する必要があります。

ダイクストラのアルゴリズムを使用すると、1回のパスでツリー全体を計算することも可能であることに注意してください。

于 2010-03-04T10:44:35.347 に答える
3

バッテリーの最小化を考慮しない場合、探しているのは最短パススパニングツリーです。これは、「コスト」関数が異なることを除けば、最小スパニングツリーに似ています。（コストは常に正のように見えるため、ダイクストラのアルゴリズムを実行して最短経路スパニングツリーを計算できます。）

ただし、これはバッテリーの最小化を考慮していません。その場合（そして、最初に最小化しようとしているのが何であるかはよくわかりません）、最小コストの最大フローを調べたいと思うかもしれません。ただし、これにより、コストを最小化する前に、最初に「フロー」が最適化（最大化）されます。これは理想的かもしれないし、そうでないかもしれません。

頂点制約を作成するには（各ノードはメッセージのみを操作できます）、それぞれに頂点を追加するk2番目のグラフを作成する必要があります。フローは制約に関係なく、この場合はコストがかかります。。したがって、基本的に、元のグラフにエッジがある場合、では、これらの各エッジにエッジがあります。実際には、フローをに制限する頂点の2番目のレイヤーを作成しています。（ルートにメッセージ制約も必要な場合を除いて、ルートの特殊なケース。）G_1u_iv_iv_iu_ik+10(a,b)GG_1(u_a,v_b)k

の標準的な最大フローソリューションでG_1十分です。フローが各頂点を指すソースと1、ルートに接続されているシンクです。のmaxflowが、頂点の数である場合、 G_1（で変化する）ための解決策があります。kG_1N

于 2010-03-04T13:35:11.813 に答える
2

各エッジの重みは他のエッジの重みに依存するため、これは単なる最小全域木ではありません。また、重みの合計を最小化する必要はありませんが、単一ノードの最大重み（出力エッジの重みに入力エッジの数に1を掛けたもの）を最小化する必要があります。

各ノードは多数のメッセージを送信する必要がありますが、外部ノードから内部ノードを介してメッセージをルーティングすると、内部ノードはより多くのメッセージを送信します。すべてのノードでバッテリーの消耗を均等にするために、内部ノードは外部ノードよりもはるかに短い接続を使用する必要があります。根からの距離へのこの依存性は指数関数的だと思います。

あなたの例では、（1,2）のノードのエネルギー消費量は少ないですが、（0、 1）出力を2倍にします。

いくつかのツリー（たとえば、各ノードをルートノードに直接送信することによって形成されたツリー）から始めて、いくつかの最適化手順を実行する必要があると思います。

最適化は、決定論的に、またはシミュレーテッドアニーリングや遺伝的アルゴリズムなどの統計的手法によって可能になる場合があります。

決定論的方法は、新しいノードの重みが現在の最大ノードの重みよりも小さくなるように、現在の最悪のノードの改善を見つけようとする可能性があります。結果がグローバル最適になるような方法でこれを行うことは困難です。

シミュレーテッドアニーリングは、各ステップでノードのターゲットの数を変更することを意味しますが、構成の「良さ」が最悪のノードによって決定されるという事実によって、これが妨げられる可能性があります。候補の子で最悪のノードが十分に頻繁に影響を受けることを確認する必要があります。これは、温度が下がると難しい場合があります。

遺伝的アルゴリズムでは、「ゲノム」を各ノードのターゲットノードへのマッピングとして設計します。時間厳守の突然変異は、1つのノードのターゲットをランダムなノードに変更することで構成されます（ただし、ルートと、ルートよりも近いノードのみを考慮する必要があります）。

于 2010-03-04T13:19:26.407 に答える
1

動的なワイヤレスセンサーネットワーク（たとえば、Telosセンサーで構成されている）を使用しているかどうか疑問に思いますか？この場合、ダイクストラのようなモノリシックなものではなく、分散型の最小距離プロトコルを開発する必要があります。

AHODV（http://moment.cs.ucsb.edu/AODV/aodv.html）プロトコルのいくつかの原則を使用できると思いますが、何らかの方法でメトリックを拡張する必要があることに注意してください。ホップカウントはエネルギー消費量と関係がありますが、同時に、メッセージの送信に使用されている電力量に注意する必要があります。おそらく、メトリックの開始は、特定のパス上の各ノードでのすべての電力使用量の合計である可能性があります。コードでネットワークを設定するときは、ルーティングの特定の「方向」のパスコストを追跡し、分散プロトコルに残りを各ノードで実行させるだけです。

これにより、多数のセンサーを空中に投げることができる柔軟性が得られ、センサーがどこに着陸しても、ネットワークはメッセージパッシングに最適なエネルギー構成に収束します。

于 2010-03-04T13:44:09.763 に答える
1

最小コストの最大フロー問題として問題を定式化してみることができます。いくつかのアイデア：

ソースとして追加のダミーノードを作成し、コストと容量がゼロのエッジをこのノードからすべての非ルートノードに接続します。次に、ルートをシンクに設定し、必要に応じてすべてのエッジコストを設定します（この場合は、ユークリッド距離の2乗）。

エネルギー効率も考慮したい場合は、各ノードに入るエッジコストにその重みを追加してみてください。2つの目標（メッセージ送信のコストとエネルギー効率）を同時に最適化しようとしているため、他にどのようにそれを実行できるかわかりません。

于 2010-03-04T11:54:20.713 に答える
1

ツリーの代わりに有向非巡回グラフを使用することを検討しましたか？言い換えると、各ノードには、メッセージを送信できる複数の「親」があります。非周期的な要件により、すべてのメッセージが最終的に到着することが保証されます。あなたはワイヤレスネットワークを持っているように聞こえ、最適なソリューションを計算するための効率的なアプローチがあるので、私は尋ねます。

アプローチは線形計画法です。rをルートノードのインデックスとします。ノードi、jの場合、cijをiからjにメッセージを送信するためのエネルギーコストとします。xijを、各タイムステップでノードiからノードjに送信されるメッセージの数を表す変数とします。zを、各ノードでの最大エネルギー消費率を表す変数とします。

線形計画法は

minimize z
subject to
# the right hand side is the rate of energy consumption by i
(for all i) z >= sum over all j of cij * xij
# every node other than the root sends one more message than it receives
(for all i != r) sum over all j of xij == 1 + sum over all j of xji
# every link has nonnegative utilization
(for all i, j) xij >= 0

このLPを生成するコードをこの形式に非常によく似たもので記述できます。その後、既成のLPソルバー（無料のGLPKなど）で解決できます。

言及する価値のあるLPの機能がいくつかあります。まず、メッセージをルートに「強制」していないのは奇妙に思えるかもしれません。cij定数が正である限り、メッセージをサイクルで送信するためにエネルギーを浪費するだけなので、意味がありません。これにより、作成した有向グラフが非循環であることが保証されます。

次に、xij変数は一般に整数ではありません。メッセージの半分を送信するにはどうすればよいですか？考えられる解決策の1つは、ランダム化です。Mがノードiによって送信されるメッセージの合計レートである場合、ノードiは各メッセージを確率xij/Mでノードjに送信します。これにより、時間の経過とともに平均が確実に計算されます。もう1つの方法は、ある種の加重ラウンドロビン方式を使用することです。

于 2010-03-06T16:19:28.517 に答える
0

最小スパニングツリー？http://en.wikipedia.org/wiki/Minimum_spanning_tree

于 2010-03-04T10:46:11.863 に答える
0

私は同様の問題に取り組みましたが、ワイヤレスセンサーを使用しました。エネルギー効率の高いプロトコルであるPEGASIS（センサー情報システムの電力効率の高い収集）を使用しました。 http://www.mast.queensu.ca/~math484/projects/pastprojects/2005/presentation05_Yi_Wei.ppt [ http://www.technion.ac.il/~es/Professional/Routing_Protocols_for_Sensor_Networks.ppt] [2]

于 2010-03-05T01:27:20.543 に答える