OLD | NEW |
(Empty) | |
| 1 /* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */ |
| 2 /* |
| 3 * Copyright (c) Waterford Institute of Technology, 2013, Julien Mineraud, BioFI
NT. |
| 4 * |
| 5 * This program is free software; you can redistribute it and/or modify |
| 6 * it under the terms of the GNU General Public License version 2 as |
| 7 * published by the Free Software Foundation; |
| 8 * |
| 9 * This program is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 12 * GNU General Public License for more details. |
| 13 * |
| 14 * You should have received a copy of the GNU General Public License |
| 15 * along with this program; if not, write to the Free Software |
| 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 17 * |
| 18 * Author: Julien Mineraud <julien.mineraud@gmail.com> |
| 19 * |
| 20 * Acknowledgements: |
| 21 * This work has received support from Science Foundation Ireland via the |
| 22 * "A Biologically inspired framework supporting network management for |
| 23 * the Future Internet" starting investigator award (grant no. 09/SIRG/I1643). |
| 24 */ |
| 25 |
| 26 #include "ga-core-calculator.h" |
| 27 #include "ns3/log.h" |
| 28 #include "ns3/trace-source-accessor.h" |
| 29 #include "ns3/channel-list.h" |
| 30 #include "ns3/node-list.h" |
| 31 #include "ns3/point-to-point-channel.h" |
| 32 #include "ns3/point-to-point-net-device.h" |
| 33 #include "ns3/ipv4-pgbr-hop-count-manager.h" |
| 34 #include "ns3/random-variable.h" |
| 35 |
| 36 NS_LOG_COMPONENT_DEFINE ("PgbrGaCoreCalculator"); |
| 37 |
| 38 namespace ns3 { |
| 39 namespace pgbr { |
| 40 |
| 41 NS_OBJECT_ENSURE_REGISTERED (GaCoreCalculator); |
| 42 |
| 43 TypeId |
| 44 GaCoreCalculator::GetTypeId (void) |
| 45 { |
| 46 static TypeId tid = |
| 47 TypeId ("ns3::pgbr::GaCoreCalculator") |
| 48 .SetParent<ObjectBase> () |
| 49 .AddConstructor<GaCoreCalculator> () |
| 50 .AddTraceSource ("GenerationTrace", "This trace helps when a new generatio
n has been calculated", |
| 51 MakeTraceSourceAccessor (&GaCoreCalculator::m_generationTrace) |
| 52 ) |
| 53 ; |
| 54 return tid; |
| 55 } |
| 56 |
| 57 GaCoreCalculator::GaCoreCalculator () |
| 58 : m_maxEnergy (1), m_energyRouter (0), m_energyLineCard (0) |
| 59 {} |
| 60 |
| 61 TypeId |
| 62 GaCoreCalculator::GetInstanceTypeId (void) const |
| 63 { |
| 64 return GetTypeId (); |
| 65 } |
| 66 |
| 67 GaCoreCalculator::~GaCoreCalculator () |
| 68 {} |
| 69 |
| 70 void |
| 71 GaCoreCalculator::Initialise (double_t energyRouter, double_t energyLineCard) |
| 72 { |
| 73 m_energyRouter = energyRouter; |
| 74 m_energyLineCard = energyLineCard; |
| 75 NS_ASSERT (energyRouter > 0 && energyLineCard > 0); |
| 76 |
| 77 uint32_t *nodesCounter = new uint32_t [NodeList::GetNNodes ()]; |
| 78 for (uint32_t i = 0; i < NodeList::GetNNodes (); i++) |
| 79 { |
| 80 nodesCounter[i] = 0; |
| 81 } |
| 82 |
| 83 //At the moment, this would work only for the point-to-point netDevices; |
| 84 ChannelList::Iterator channelIter; |
| 85 for (channelIter = ChannelList::Begin (); channelIter != ChannelList::End ();
channelIter++) |
| 86 { |
| 87 Ptr<PointToPointChannel> p2pChannel = DynamicCast<PointToPointChannel> (*cha
nnelIter); |
| 88 if (p2pChannel) |
| 89 { |
| 90 for (uint32_t i = 0 ; i < p2pChannel->GetNDevices (); i++) |
| 91 { |
| 92 uint32_t nodeId = p2pChannel->GetDevice (i)->GetNode ()->GetId (); |
| 93 nodesCounter[nodeId]++; |
| 94 } |
| 95 } |
| 96 } |
| 97 |
| 98 m_maxEnergy = 0.0; |
| 99 for (uint32_t i = 0; i < NodeList::GetNNodes (); i++) |
| 100 { |
| 101 if (nodesCounter[i] > 0) |
| 102 { |
| 103 m_maxEnergy += m_energyRouter + (nodesCounter[i] + 1) * m_energyLineCard; |
| 104 } |
| 105 } |
| 106 |
| 107 delete [] nodesCounter; |
| 108 |
| 109 Ipv4HopCountManager::Initialise (); |
| 110 } |
| 111 |
| 112 GaCoreCalculator::Chromosome |
| 113 GaCoreCalculator::GenerateChromosome (std::vector<uint32_t> egressNodes) |
| 114 { |
| 115 /** |
| 116 * This function works as follow. |
| 117 * 1. Random selection of 2 egress nodes, and find a ECMP connecting the two e
gress nodes |
| 118 */ |
| 119 |
| 120 NS_ASSERT (egressNodes.size () >= 2); |
| 121 Chromosome chromosome; |
| 122 |
| 123 //Step 1: find 2 random egress nodes |
| 124 UniformVariable egressSelection; |
| 125 |
| 126 double_t step = 1.0 / egressNodes.size (); |
| 127 double_t temp = step; |
| 128 std::vector<uint32_t>::iterator egressIter = egressNodes.begin (); |
| 129 double_t egressSelectionValue = egressSelection.GetValue (); |
| 130 while (temp < egressSelectionValue) |
| 131 { |
| 132 temp += step; |
| 133 egressIter++; |
| 134 } |
| 135 NS_ASSERT (egressIter != egressNodes.end ()); |
| 136 Ptr<Node> egress1 = NodeList::GetNode (*egressIter); |
| 137 egressNodes.erase (egressIter); |
| 138 |
| 139 step = 1.0 / egressNodes.size (); |
| 140 temp = step; |
| 141 egressIter = egressNodes.begin (); |
| 142 egressSelectionValue = egressSelection.GetValue (); |
| 143 while (temp < egressSelectionValue) |
| 144 { |
| 145 temp += step; |
| 146 egressIter++; |
| 147 } |
| 148 NS_ASSERT (egressIter != egressNodes.end ()); |
| 149 Ptr<Node> egress2 = NodeList::GetNode (*egressIter); |
| 150 egressNodes.erase (egressIter); |
| 151 |
| 152 //Step 2: Find the equal cost shortest path for the two egress nodes. |
| 153 AddEqualCostShortestPath (egress1, egress2, chromosome); |
| 154 |
| 155 //Step 3: while there are egress nodes to pick, select a random one, then conn
ect it to a random node of the chromosome |
| 156 while (!egressNodes.empty ()) |
| 157 { |
| 158 step = 1.0 / egressNodes.size (); |
| 159 temp = step; |
| 160 egressIter = egressNodes.begin (); |
| 161 egressSelectionValue = egressSelection.GetValue (); |
| 162 while (temp < egressSelectionValue) |
| 163 { |
| 164 temp += step; |
| 165 egressIter++; |
| 166 } |
| 167 NS_ASSERT (egressIter != egressNodes.end ()); |
| 168 Ptr<Node> egress = NodeList::GetNode (*egressIter); |
| 169 egressNodes.erase (egressIter); |
| 170 |
| 171 if (std::find (chromosome.nodes.begin (), chromosome.nodes.end (), egress) !
= chromosome.nodes.end ()) |
| 172 { |
| 173 //We dont need to connect the egress if it's already connected |
| 174 continue; |
| 175 } |
| 176 |
| 177 //Randomly select a dest to connect the egress node to the connected nodes o
f the chromosome |
| 178 step = 1.0 / chromosome.nodes.size (); |
| 179 temp = step; |
| 180 std::vector<Ptr<Node> >::iterator destNodeIt = chromosome.nodes.begin (); |
| 181 egressSelectionValue = egressSelection.GetValue (); |
| 182 while (temp < egressSelectionValue) |
| 183 { |
| 184 temp += step; |
| 185 destNodeIt++; |
| 186 } |
| 187 NS_ASSERT (destNodeIt != chromosome.nodes.end ()); |
| 188 AddEqualCostShortestPath (egress, *destNodeIt, chromosome); |
| 189 } |
| 190 return chromosome; |
| 191 } |
| 192 |
| 193 void |
| 194 GaCoreCalculator::AddEqualCostShortestPath (Ptr<Node> egressToConnect, Ptr<Node>
egressConnected, Chromosome &chromosome) |
| 195 { |
| 196 UniformVariable equalCostNeighbourSelectionVariable; |
| 197 //We have to stop adding links and nodes to chromosome, when the output of the
channel is already in the chromosome |
| 198 Ptr<Node> currentNode = egressToConnect; |
| 199 |
| 200 if (std::find (chromosome.nodes.begin (), chromosome.nodes.end (), egressConne
cted) == chromosome.nodes.end ()) |
| 201 { |
| 202 chromosome.nodes.push_back (egressConnected); |
| 203 } |
| 204 |
| 205 while (std::find (chromosome.nodes.begin (), chromosome.nodes.end (), currentN
ode) == chromosome.nodes.end ()) |
| 206 { |
| 207 uint32_t distanceToDest = Ipv4HopCountManager::GetHopCount (currentNode, egr
essConnected); |
| 208 //find all the neighbours of current node that has a distance to dest of "di
stanceToDest - 1" |
| 209 std::vector<Ptr<NetDevice> > potentialNeighbours; |
| 210 uint32_t minDist = -1; |
| 211 for (uint32_t i = 0; i < currentNode->GetNDevices (); i++) |
| 212 { |
| 213 Ptr<NetDevice> currentNetDev = currentNode->GetDevice (i); |
| 214 if (!currentNetDev->IsPointToPoint ()) |
| 215 { |
| 216 continue; |
| 217 } |
| 218 Ptr<NetDevice> neighbourNetDev = currentNetDev->GetChannel()->GetDevice (0
) == currentNetDev ? |
| 219 currentNetDev->GetChannel()->GetDevice (1) : currentNetDev->GetChannel
()->GetDevice (0); |
| 220 uint32_t tempDist = Ipv4HopCountManager::GetHopCount (neighbourNetDev->Get
Node (), egressConnected); |
| 221 if (tempDist < minDist) |
| 222 { |
| 223 minDist = tempDist; |
| 224 } |
| 225 if (tempDist == distanceToDest - 1) |
| 226 { |
| 227 potentialNeighbours.push_back (neighbourNetDev); |
| 228 } |
| 229 } |
| 230 NS_ASSERT_MSG (!potentialNeighbours.empty (), "Empty with minDist = " << min
Dist << " and distnceToDest = " << distanceToDest); |
| 231 |
| 232 double_t step = 1.0 / potentialNeighbours.size (); |
| 233 double_t temp = step; |
| 234 std::vector<Ptr<NetDevice> >::iterator potentialNeighbourit = potentialNeigh
bours.begin (); |
| 235 double_t equalCostNeighbourSelectionValue = equalCostNeighbourSelectionVaria
ble.GetValue (); |
| 236 while (temp < equalCostNeighbourSelectionValue) |
| 237 { |
| 238 temp += step; |
| 239 potentialNeighbourit++; |
| 240 } |
| 241 NS_ASSERT (potentialNeighbourit != potentialNeighbours.end ()); |
| 242 |
| 243 //Now add the corresponding channel |
| 244 NS_ASSERT (std::find (chromosome.links.begin (), chromosome.links.end (), (*
potentialNeighbourit)->GetChannel ()) == chromosome.links.end ()); |
| 245 chromosome.links.push_back ((*potentialNeighbourit)->GetChannel ()); |
| 246 chromosome.nodes.push_back (currentNode); |
| 247 currentNode = (*potentialNeighbourit)->GetNode (); |
| 248 } |
| 249 } |
| 250 |
| 251 void |
| 252 GaCoreCalculator::GenerateInitialPopulation (std::vector<uint32_t> egressNodes,
uint32_t populationSize) |
| 253 { |
| 254 for (uint32_t i = 0; i < populationSize; i++) |
| 255 { |
| 256 Chromosome chromosome = GenerateChromosome (egressNodes); |
| 257 PruneChromosome (chromosome); |
| 258 m_population.push_back (chromosome); |
| 259 } |
| 260 } |
| 261 |
| 262 GaCoreCalculator::Chromosome |
| 263 GaCoreCalculator::GetBestChromosome () |
| 264 { |
| 265 NS_ASSERT (!m_population.empty ()); |
| 266 double_t minEnergy = m_maxEnergy; |
| 267 Chromosome chromosome; |
| 268 for (std::vector<Chromosome>::iterator it = m_population.begin (); it != m_pop
ulation.end (); it++) |
| 269 { |
| 270 double energy = GetEnergy (*it); |
| 271 if (energy < minEnergy) |
| 272 { |
| 273 minEnergy = energy; |
| 274 chromosome = *it; |
| 275 } |
| 276 } |
| 277 std::cout << "The energy reduction of the best chromosome is " << (minEnergy /
m_maxEnergy) << " and max is " << m_maxEnergy << "\n"; |
| 278 return chromosome; |
| 279 } |
| 280 |
| 281 double_t |
| 282 GaCoreCalculator::GetEnergy (const Chromosome &chromosome) const |
| 283 { |
| 284 uint32_t *nodesCounter = new uint32_t [NodeList::GetNNodes ()]; |
| 285 for (uint32_t i = 0; i < NodeList::GetNNodes (); i++) |
| 286 { |
| 287 nodesCounter[i] = 0; |
| 288 } |
| 289 |
| 290 std::vector<Ptr<Channel> >::const_iterator iter; |
| 291 for (iter = chromosome.links.begin (); iter != chromosome.links.end (); iter++
) |
| 292 { |
| 293 for (uint32_t i = 0; i < (*iter)->GetNDevices (); i++) |
| 294 { |
| 295 nodesCounter[(*iter)->GetDevice (i)->GetNode ()->GetId ()]++; |
| 296 } |
| 297 } |
| 298 |
| 299 double_t energy = 0.0; |
| 300 for (uint32_t i = 0; i < NodeList::GetNNodes (); i++) |
| 301 { |
| 302 if (nodesCounter[i] > 0) |
| 303 { |
| 304 energy += m_energyRouter + (nodesCounter[i] + 1) * m_energyLineCard; |
| 305 } |
| 306 } |
| 307 delete [] nodesCounter; |
| 308 return energy; |
| 309 } |
| 310 |
| 311 void |
| 312 GaCoreCalculator::PruneChromosome (Chromosome &chromosome) |
| 313 { |
| 314 //We run the Prim algorithm for MST |
| 315 std::vector<Ptr<Node> > newNodes; |
| 316 std::vector<Ptr<Channel> > channels; |
| 317 std::vector<Ptr<Channel> > newChannels; |
| 318 |
| 319 NS_ASSERT (!chromosome.nodes.empty ()); |
| 320 newNodes.push_back (chromosome.nodes[0]); |
| 321 |
| 322 while (newNodes.size () != chromosome.nodes.size ()) |
| 323 { |
| 324 std::vector<Ptr<Channel> >::iterator iter; |
| 325 for (iter = chromosome.links.begin (); iter != chromosome.links.end ();) |
| 326 { |
| 327 Ptr<Channel> channel = *iter; |
| 328 Ptr<Node> u = channel->GetDevice (0)->GetNode (); |
| 329 Ptr<Node> v = channel->GetDevice (1)->GetNode (); |
| 330 bool uInNewNodes = std::find (newNodes.begin (), newNodes.end (), u) != ne
wNodes.end (); |
| 331 bool vInNewNodes = std::find (newNodes.begin (), newNodes.end (), v) != ne
wNodes.end (); |
| 332 if ((uInNewNodes && !vInNewNodes) || (!uInNewNodes && vInNewNodes)) |
| 333 { |
| 334 if (!uInNewNodes) |
| 335 { |
| 336 newNodes.push_back (u); |
| 337 } |
| 338 else |
| 339 { |
| 340 newNodes.push_back (v); |
| 341 } |
| 342 newChannels.push_back (channel); |
| 343 iter = chromosome.links.erase (iter); |
| 344 break; |
| 345 } |
| 346 else |
| 347 { |
| 348 ++iter; |
| 349 } |
| 350 } |
| 351 } |
| 352 chromosome.links = newChannels; |
| 353 } |
| 354 |
| 355 std::pair<GaCoreCalculator::Chromosome, GaCoreCalculator::Chromosome> |
| 356 GaCoreCalculator::CrossOver (const Chromosome &chromosome1, const Chromosome &ch
romosome2) |
| 357 { |
| 358 //In this function I want to pick all the Channels that are common to both chr
omosome |
| 359 std::vector<Ptr<Channel> > commomChannels; |
| 360 for (std::vector<Ptr<Channel> >::const_iterator channelIter = chromosome1.link
s.begin (); channelIter != chromosome1.links.end (); channelIter++) |
| 361 { |
| 362 if (std::find (chromosome2.links.begin (), chromosome2.links.end (), *channe
lIter) != chromosome2.links.end ()) |
| 363 { |
| 364 commomChannels.push_back (*channelIter); |
| 365 } |
| 366 } |
| 367 if (commomChannels.empty ()) |
| 368 { |
| 369 return std::make_pair (chromosome1, chromosome2); |
| 370 } |
| 371 |
| 372 double_t step = 1.0 / commomChannels.size (); |
| 373 double_t temp = step; |
| 374 |
| 375 std::vector<Ptr<Channel> >::iterator commonChannelIt = commomChannels.begin ()
; |
| 376 UniformVariable commomChannelRandomSelection; |
| 377 double_t commomChannelRandomSelectionValue = commomChannelRandomSelection.GetV
alue (); |
| 378 while (temp < commomChannelRandomSelectionValue) |
| 379 { |
| 380 temp += step; |
| 381 commonChannelIt++; |
| 382 } |
| 383 NS_ASSERT (commonChannelIt != commomChannels.end ()); |
| 384 |
| 385 //Now I need to crossover the two chromosome on that channel. |
| 386 return std::make_pair (chromosome1, chromosome2); |
| 387 } |
| 388 |
| 389 }} //namespace pgbr, ns3 |
OLD | NEW |