量消耗可以表示为: ( ) e r a R ?? ?(9) 其中 0a?。节点的通信半径越大,节点的能量消耗也越多。因此,从节能角度考虑,在保证能够满足节点间通信条件的基础上,节点的通信半径越小,节点的能量消耗也越少。因此,本文可以引用最小生成树的贪心策略解决该问题。贪心策略: 最近顶点策略,任选一个顶点,并以此建立起生成树,每一步的贪心选择是简单地把不在生成树中的最近顶点添加到生成树种。根据该贪心策略本文采用了 Prim 算法,即使生成树以一种自然的方式生长,即从任意顶点开始,每一步为这棵树添加以个分枝,直到生成树中包含全部顶点,同过该算法我们的到如下图 5最小生成树路径图。 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 最小生成树路径图图 5:最小生成树路径图根据最小生成树路径图,我们可以得到在节约能源的情况下任意两个节点间的通信通路,如下表 5所示:
全文预览
