가장 에너지 효율적인 ad-hoc 네트워크를 계산하는 알고리즘

Question

나는 각각 자신의 고정 된 위치를 가진 N 개의 노드를 가진 (이론적 인) 네트워크를 가지고 있습니다. 각 노드는 사이클 당 하나의 메시지를 보내고 직접 또는 다른 노드를 통해 루트에 도달해야합니다.

노드 A에서 노드 B로 메시지를 보내는 데 드는 에너지 비용은 두 노드 사이의 거리를 제곱합니다.

도전 과제는 이러한 노드를 트리 형식으로 연결하여 에너지 효율적인 네트워크를 만드는 방법입니다.

예. 이 노드들을 연결할 수있는 두 가지 방법이 있으며, 왼쪽은 에너지 효율이 더 높습니다.

유전자 알고리즘을 사용하여 문제를 해결하기 위해 노력하고 있지만 다른 아이디어가 있거나 다른 관련 오픈 소스 코드를 알고 있는지 궁금합니다.

편집 : 네트워크의 또 다른 측면은 각 노드가 배터리로 작동한다는 점입니다. 따라서 동일한 노드를 통해 라우팅되는 메시지가 너무 많으면 해당 노드의 배터리가 고갈되어 네트워크가 작동하지 않게됩니다. 네트워크의 에너지 효율은 노드가 배터리를 모두 소모하기 전에 각 노드에서 루트로 성공적으로 전송할 수있는 메시지 수에 의해 측정됩니다.

편집 # 2 : 질문의 원본 텍스트에서 죄송합니다. 그것으로 말미암아, 이전의 대답들 중 일부는 내가 찾던 것이 아니지만 MST 알고리즘에 익숙하지 않았기 때문에 그들에 대해 알려 줘서 고마워. 명확 일들이 나를이를 추가 할 수 있도록 만드는 희망에서

는 :

모든 노드는 내부 노드를 포함하여, 사이클 당 자신의 하나의 메시지를 보냅니다. 내부 노드는받은 메시지를 중계 할 책임이 있습니다. 이것은 배터리의 변형에 추가됩니다. 추가 메시지를 보내고있는 경우입니다. 목표는 노드의 배터리가 소모되기 전에 실행되는 사이클의 양을 최대화하는 것입니다.

Answer 1

배터리 최소화를 고려하지 않고 찾고자하는 것이 Minimum Spanning Tree과 비슷하지만 다른 "비용"기능을 제외하고는 Shortest Path Spanning Tree과 비슷합니다. (비용이 항상 양의 값을 갖기 때문에 을 실행하여 최단 경로 스패닝 트리를 계산할 수 있습니다.)

그러나 배터리 최소화는 고려하지 않았습니다. 이 경우 (처음에는 최소화하려는 것이 무엇인지 잘 모르겠습니다) Min-cost max flow을 조사하고 싶을 수도 있습니다. 그러나 비용을 최소화하기 전에 먼저 "흐름"을 최적화 (최대화)합니다. 이것은 이상적 일 수도 있고 아닐 수도 있습니다. 무엇이든 제약이 될 u_i과 흐름 v_i을 가진 -

는 버텍스 제약 (각 노드는 k 메시지를 작동 할 수 있습니다), 당신은 당신이 각 v_i에 대한 추가 정점 u_i를 추가 번째 그래프 G_1를 작성해야 만들려면 이 경우 k+1이고, 비용은 0입니다. 기본적으로 G의 원래 그래프에 (a,b) 모서리가있는 경우 G_1에 각 모서리에 대해 (u_a,v_b) 모서리가 있습니다. 실제로, 흐름을 k으로 제한하는 두 번째 정점 레이어를 만듭니다. (루트에 대한 메시지 제약을 원하지 않는 한 특별한 경우입니다.)

G_1의 표준 최대 유량 솔루션으로 충분해야합니다 - 흐름이 각 정점을 가리키는 소스는 1이고 싱크 이는 루트에 연결됩니다.최대 유량이 G_1 인 경우 G_1 (변동 값은 k)에 대한 해결책은 정점 수인 N입니다.

Answer 2

전체 그래프를 구성한 다음 각 노드에서 Dijkstra's shortest path algorithm을 사용하면 해당 노드의 최소 비용 경로를 찾을 수 있다고 생각합니다. 이 경로의 결합은 최소 비용 트리를 형성해야합니다.

Dijkstra의 알고리즘을 사용하면 한 번에 전체 트리를 계산할 수 있습니다.

Answer 3

최소 스패닝 트리? http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 4

최소 비용 최대 플로우 문제로 문제를 공식화 해보십시오. 단지 몇 가지 아이디어가 있습니다 :

소스로 더미 노드를 추가로 만들고이 노드에서 비용이 0이고 용량이 1 인 에지를 모든 비 루트 노드에 연결하십시오. 그런 다음 싱크에서 루트를 설정하고 원하는 모든 에지 비용을 설정합니다 (이 경우 유클리드 거리의 제곱).

또한 에너지 효율을 고려하려면 각 노드로 들어가는 가장자리 비용에 가중치를 더할 수 있습니다. 동시에 두 가지 목표 (메시지 전송 비용과 에너지 효율성)를 최적화하려고하기 때문에 어떻게 할 수 있는지 잘 모르겠습니다.

Answer 5

각 에지의 가중치가 다른 에지의 가중치에 따라 좌우되기 때문에 최소 스패닝 트리가 아닙니다. 또한 가중치의 합을 최소화 할 필요는 없지만 출력 에지의 가중치 인 단일 노드의 최대 가중치에 수신 에지 수를 곱한 값을 더하면됩니다.

각 노드는 많은 수의 메시지를 전송해야하지만 외부 노드에서 내부 노드를 통해 메시지를 라우팅하면 내부 노드가 더 많은 메시지를 전송합니다. 모든 노드에서 배터리 드레인을 균등하게하려면 내부 노드가 외부 노드보다 훨씬 짧은 연결을 사용해야합니다. 루트로부터의 거리에 대한 이러한 의존성이 기하 급수적이라고 생각합니다.

예에서 주어진 측정 값 (최대 메시지 수)에 따라 왼쪽 큐브가 더 효율적인지 여부는 분명하지 않습니다. 왜냐하면 (1,2) 노드의 에너지 소비가 적기 때문에 at (0, 1)은 출력을 두 배로 만듭니다.

여러 트리 (예 : 각 노드를 루트 노드에 직접 전송함으로써 형성되는 트리)로 시작한 다음 여러 가지 최적화 단계를 수행해야한다고 생각합니다.

최적화는 결정적으로 또는 시뮬레이션 어닐링 또는 유전 알고리즘과 같은 통계적 방법을 통해 가능할 수 있습니다.

결정 론적 방법은 새로운 노드 가중치가 현재 최대 노드 가중치보다 작도록 현재의 최악 노드에 대한 개선을 찾으려고 시도합니다. 결과가 글로벌 최적이되도록하는 것은 어렵습니다.

시뮬레이션 된 어닐링은 각 단계에서 노드의 대상 수를 변경하는 것을 의미하지만 구성의 "장점"이 최악의 노드에 의해 결정된다는 사실에 의해 방해받을 수 있습니다. 최악의 노드가 후보 자녀에게서 충분히 영향을 받는지 확인해야합니다. 온도가 떨어지면 어려울 수 있습니다.

유전자 알고리즘에서 각 노드의 대상 노드에 대한 매핑으로 "게놈"을 디자인 할 것입니다. 시간 엄 밀한 돌연변이는 한 노드의 목표를 임의의 노드로 변경하는 것으로 구성됩니다 (단, 루트와 루트보다 가까운 노드 만 고려해야 함).

Answer 6

동적 무선 센서 네트워크 (예 : Telos 센서로 구성)를 사용하고 있는지 궁금합니다. 이 경우, 당신은 Dijkstra와 같은 더 획일적 인 것보다는 분산 된 min-distance 프로토콜을 개발하기를 원할 것입니다.

나는 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의 경우 i를 j로 보내는 메시지의 에너지 비용을 cij라고 합니다. xij는 각 시간 단계에서 노드 i가 노드 j로 보낸 메시지 수를 나타내는 변수가되게합니다. z를 각 노드에서 에너지 소비의 최대 비율을 나타내는 변수 라하자.

선형 프로그램은이 (기성 LP 솔버에 의해 해결 될 수 그러자

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를 생성하는 코드를 작성할 수 있습니다 예를 들어, 무료 GLPK).

언급 할 가치가있는 LP의 몇 가지 기능이 있습니다. 첫째, 우리가 메시지를 뿌리로 이동시키지 않았다는 것이 이상하게 보일 수 있습니다. cij 상수가 양수이면 주기적으로 메시지를 보내는 데 낭비가되는 것으로 밝혀졌습니다. 따라서 요점은 없습니다. 이것은 또한 우리가 생성 한 유향 그래프가 비순환적임을 보장합니다.

둘째, xij 변수는 일반적으로 정수가 아닙니다. 우리는 어떻게 메시지를 반으로 보냅니 까? 하나의 가능한 해법은 랜덤 화이다 : M이 노드 i에 의해 전송 된 메시지의 총 비율이라면, 노드 i는 확률 xij/M으로 각 메시지를 노드 j에 보낸다. 이렇게하면 시간이 지남에 따라 평균이 잘 작동합니다. 또 다른 대안은 일종의 가중 라운드 로빈 방식을 사용하는 것입니다.