計算最節能的ad-hoc網絡的算法

Question

我有一個具有N個節點的（理論）網絡，每個節點都有自己的固定位置。每個節點每個週期發送一條消息，需要直接或通過其他節點到達根節點。

從節點A發送消息到節點B的能量消耗是它們之間的距離，平方。

面臨的挑戰是如何將這些節點以樹形格式連接起來，以生產最節能的網絡。

E.g.這裏有兩種可能的方式來鏈接這些節點，其中左邊節點更節能。

我正在研究遺傳算法來解決這個問題，但我想知道是否有人有任何其他想法，或者知道任何相關的開源代碼。

編輯：我忘記提及的網絡的另一個方面是，每個節點都由電池供電。因此，如果我們有太多的消息通過同一個節點路由，那麼該節點的電池將耗盡，導致網絡出現故障。網絡的能源效率是衡量在每個節點電池耗盡之前，從每個節點到根的成功傳輸數量。

編輯＃2：對於問題原文中的遺漏，我感到抱歉。因爲它，你以前的一些答案不是我正在尋找的，但我不熟悉MST算法，所以謝謝你告訴我他們。

在做事情更清晰，讓我補充這樣的希望：

所有節點發送自己的一個消息每個週期，包括內部節點。內部節點還負責中繼他們收到的任何消息。這增加了他們電池的負擔，如果他們發送了他們自己的額外信息。目標是在任何節點的電池耗盡之前使所獲得的週期數量最大化。

Answer 1

在不考慮電池最小化的情況下，您要尋找的是Shortest Path Spanning Tree，它與Minimum Spanning Tree類似，但具有不同的「成本」功能。 （您可以運行Dijkstra's Algorithm來計算最短路徑生成樹，因爲成本似乎總是正數。）

儘管如此，這並沒有考慮電池最小化。在這種情況下，（我不太確定你想要最小化的是什麼），你可能想看看Min-cost max flow。但是，這將在最小化成本之前首先優化（最大化）「流量」。這可能也可能不是理想的。

要創建頂點約束（每個節點只能操作k消息），你只需要創建在您添加一個頂點u_i每個v_i第二圖形G_1 - 並且具有流動v_i到u_i是無論你的約束在這種情況下爲k+1，成本爲0。因此，基本上，如果在原始圖G邊緣(a,b)，然後在G_1，會有對每個這些邊緣的邊緣(u_a,v_b)。實際上，您正在創建第二層頂點，以將流量限制爲k。 （特殊情況爲根，除非你還需要在根的消息約束。）

上G_1標準最大流解決方案應該是足夠的 - 它指向了的1一個流中的每個頂點的源極，和一個接收器連接到根。如果G_1的最大流量是N（頂點的數量），則存在針對G_1（根據k變化）的解決方案。

Answer 2

我認爲你可以構建完整的圖形，然後在每個節點上使用Dijkstra's shortest path algorithm來找到該節點的最低成本路由。這些路徑的聯合應該形成最小成本樹。

請注意，使用Dijkstra算法也可以一次計算整個樹。

Answer 3

最小生成樹？ http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 4

您可以嘗試將問題描述爲最小成本最大流量問題。只是一些想法：

創建一個額外的虛擬節點作爲源，並將零成本和容量1的邊緣從此節點連接到每個非根節點。然後在水槽處設置根，並根據需要設置所有邊緣成本（本例中爲歐幾里得距離的平方）。

如果您還想考慮能源效率，則可以嘗試爲進入每個節點的邊緣成本添加權重。我不確定你還能做什麼，因爲你正試圖同時優化兩個目標（消息發送成本和能源效率）。

Answer 5

這不僅僅是一個最小生成樹，因爲每個邊的權重取決於其他邊的權重。此外，您不需要最小化權重總和，而是將單個節點上的最大權重（它的輸出邊的權重）乘以輸入邊的數量加上一。

每個節點都必須傳輸多個消息，但是如果通過內部節點從外部節點路由消息，則內部節點將傳輸更多數量的消息。爲了均衡所有節點上的電池消耗，內部節點將不得不使用比外部節點更短的連接;我懷疑對距離根的距離的依賴是指數級的。

在你的例子，它不是那麼清楚左邊一個人是否是你給的測量（消息的最大數量）更有效，因爲同時在（1,2）的節點具有能耗少，一（0,1）的輸出翻倍。

我相信你必須從某棵樹開始（例如，通過讓每個節點直接傳輸到根節點而形成的樹），然後進行一些優化步驟。

優化可能是確定性的或通過統計方法如模擬退火或遺傳算法。

確定性方法可能會試圖找到當前最差節點的改進，使得新節點權重小於當前最大節點權重。要做到這一點很難，其結果是全球最佳。

模擬退火將意味着在每一步改變的若干節點的目標，但是這可能是由所涉及的結構的‘良好性’是通過其最壞節點確定的事實而受到阻礙。您需要確保候選兒童中最糟糕的節點經常受到影響，這在溫度下降時可能會很困難。

在遺傳算法中，您可以將「基因組」設計爲每個節點到其目標節點的映射。準時突變可能包括將一個節點的目標更改爲隨機節點（但只應考慮比根更近的根節點和節點）。

Answer 6

我想知道您是否使用動態無線傳感器網絡（例如Telos傳感器組成）？如果是這樣的話，你會想要開發一個分佈式的最小距離協議，而不是像Dijkstra那樣更加單一的東西。

我相信你可以使用AHODV（http://moment.cs.ucsb.edu/AODV/aodv.html）協議的一些原則，但請記住，你需要以某種方式增加指標。跳數與能耗有很大關係，但與此同時，您需要記住傳輸消息的功率有多大。也許一個度量的開始可能是給定路徑上每個節點的所有功率用法的總和。當您的代碼設置網絡時，您只需跟蹤路由的給定「方向」的路徑成本，並讓您的分佈式協議在每個節點上完成其餘任務。

這使您可以靈活地將一堆傳感器拋在空中，無論它們落在何處，網絡都將匯聚在消息傳遞的最佳能量配置上。

Answer 7

我從事類似的問題，但使用無線傳感器。我們使用了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]

Answer 8

你有使用向無環圖，而不是一棵樹的考慮？換句話說，每個節點都有多個可以發送消息的「父母」 - 非循環需求確保所有消息最終到達。我問，因爲它聽起來像你有一個無線網絡，因爲有一個有效的方法來計算最佳的解決方案。

該方法是線性規劃。設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變量通常不是整數。我們如何發送一條消息？一個可能的解決方案是隨機化：如果M是節點i發送的消息的總速率，則節點i以概率xij/M將每個消息發送到節點j。這可確保平均值隨時間變化。另一種選擇是使用某種加權循環機制。