550 { |
550 { |
551 N2.push_back (*twoHopNeigh); |
551 N2.push_back (*twoHopNeigh); |
552 } |
552 } |
553 } |
553 } |
554 |
554 |
555 NS_LOG_DEBUG ("Size of N2: " << N2.size ()); |
555 #ifdef NS3_LOG_ENABLE |
|
556 { |
|
557 std::ostringstream os; |
|
558 os << "["; |
|
559 for (TwoHopNeighborSet::const_iterator iter = N2.begin (); |
|
560 iter != N2.end (); iter++) |
|
561 { |
|
562 TwoHopNeighborSet::const_iterator next = iter; |
|
563 next++; |
|
564 os << iter->neighborMainAddr << "->" << iter->twoHopNeighborAddr; |
|
565 if (next != N2.end ()) |
|
566 os << ", "; |
|
567 } |
|
568 os << "]"; |
|
569 NS_LOG_DEBUG ("N2: " << os.str ()); |
|
570 } |
|
571 #endif //NS3_LOG_ENABLE |
556 |
572 |
557 // 1. Start with an MPR set made of all members of N with |
573 // 1. Start with an MPR set made of all members of N with |
558 // N_willingness equal to WILL_ALWAYS |
574 // N_willingness equal to WILL_ALWAYS |
559 for (NeighborSet::const_iterator neighbor = N.begin (); neighbor != N.end (); neighbor++) |
575 for (NeighborSet::const_iterator neighbor = N.begin (); neighbor != N.end (); neighbor++) |
560 { |
576 { |
582 // (we do this later) |
598 // (we do this later) |
583 |
599 |
584 // 3. Add to the MPR set those nodes in N, which are the *only* |
600 // 3. Add to the MPR set those nodes in N, which are the *only* |
585 // nodes to provide reachability to a node in N2. |
601 // nodes to provide reachability to a node in N2. |
586 std::set<Ipv4Address> coveredTwoHopNeighbors; |
602 std::set<Ipv4Address> coveredTwoHopNeighbors; |
587 for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); twoHopNeigh++) |
603 for (TwoHopNeighborSet::const_iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); twoHopNeigh++) |
588 { |
604 { |
589 NeighborSet::const_iterator onlyNeighbor = N.end (); |
605 bool onlyOne = true; |
590 |
606 // try to find another neighbor that can reach twoHopNeigh->twoHopNeighborAddr |
591 for (NeighborSet::const_iterator neighbor = N.begin (); |
607 for (TwoHopNeighborSet::const_iterator otherTwoHopNeigh = N2.begin (); otherTwoHopNeigh != N2.end (); otherTwoHopNeigh++) |
592 neighbor != N.end (); neighbor++) |
608 { |
593 { |
609 if (otherTwoHopNeigh->twoHopNeighborAddr == twoHopNeigh->twoHopNeighborAddr |
594 if (neighbor->neighborMainAddr == twoHopNeigh->neighborMainAddr) |
610 && otherTwoHopNeigh->neighborMainAddr != twoHopNeigh->neighborMainAddr) |
595 { |
611 { |
596 if (onlyNeighbor == N.end ()) |
612 onlyOne = false; |
|
613 break; |
|
614 } |
|
615 } |
|
616 if (onlyOne) |
|
617 { |
|
618 NS_LOG_LOGIC ("Neighbor " << twoHopNeigh->neighborMainAddr |
|
619 << " is the only that can reach 2-hop neigh. " |
|
620 << twoHopNeigh->twoHopNeighborAddr |
|
621 << " => select as MPR."); |
|
622 |
|
623 mprSet.insert (twoHopNeigh->neighborMainAddr); |
|
624 |
|
625 // take note of all the 2-hop neighbors reachable by the newly elected MPR |
|
626 for (TwoHopNeighborSet::const_iterator otherTwoHopNeigh = N2.begin (); |
|
627 otherTwoHopNeigh != N2.end (); otherTwoHopNeigh++) |
|
628 { |
|
629 if (otherTwoHopNeigh->neighborMainAddr == twoHopNeigh->neighborMainAddr) |
597 { |
630 { |
598 onlyNeighbor = neighbor; |
631 coveredTwoHopNeighbors.insert (otherTwoHopNeigh->twoHopNeighborAddr); |
599 } |
|
600 else |
|
601 { |
|
602 onlyNeighbor = N.end (); |
|
603 break; |
|
604 } |
632 } |
605 } |
633 } |
606 } |
|
607 if (onlyNeighbor != N.end ()) |
|
608 { |
|
609 mprSet.insert (onlyNeighbor->neighborMainAddr); |
|
610 coveredTwoHopNeighbors.insert (twoHopNeigh->twoHopNeighborAddr); |
|
611 } |
634 } |
612 } |
635 } |
613 // Remove the nodes from N2 which are now covered by a node in the MPR set. |
636 // Remove the nodes from N2 which are now covered by a node in the MPR set. |
614 for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); |
637 for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); |
615 twoHopNeigh != N2.end (); ) |
638 twoHopNeigh != N2.end (); ) |
616 { |
639 { |
617 if (coveredTwoHopNeighbors.find (twoHopNeigh->twoHopNeighborAddr) != coveredTwoHopNeighbors.end ()) |
640 if (coveredTwoHopNeighbors.find (twoHopNeigh->twoHopNeighborAddr) != coveredTwoHopNeighbors.end ()) |
618 { |
641 { |
|
642 NS_LOG_LOGIC ("2-hop neigh. " << twoHopNeigh->twoHopNeighborAddr << " is already covered by an MPR."); |
619 twoHopNeigh = N2.erase (twoHopNeigh); |
643 twoHopNeigh = N2.erase (twoHopNeigh); |
620 } |
644 } |
621 else |
645 else |
622 { |
646 { |
623 twoHopNeigh++; |
647 twoHopNeigh++; |
626 |
650 |
627 // 4. While there exist nodes in N2 which are not covered by at |
651 // 4. While there exist nodes in N2 which are not covered by at |
628 // least one node in the MPR set: |
652 // least one node in the MPR set: |
629 while (N2.begin () != N2.end ()) |
653 while (N2.begin () != N2.end ()) |
630 { |
654 { |
|
655 |
|
656 #ifdef NS3_LOG_ENABLE |
|
657 { |
|
658 std::ostringstream os; |
|
659 os << "["; |
|
660 for (TwoHopNeighborSet::const_iterator iter = N2.begin (); |
|
661 iter != N2.end (); iter++) |
|
662 { |
|
663 TwoHopNeighborSet::const_iterator next = iter; |
|
664 next++; |
|
665 os << iter->neighborMainAddr << "->" << iter->twoHopNeighborAddr; |
|
666 if (next != N2.end ()) |
|
667 os << ", "; |
|
668 } |
|
669 os << "]"; |
|
670 NS_LOG_DEBUG ("Step 4 iteration: N2=" << os.str ()); |
|
671 } |
|
672 #endif //NS3_LOG_ENABLE |
|
673 |
|
674 |
631 // 4.1. For each node in N, calculate the reachability, i.e., the |
675 // 4.1. For each node in N, calculate the reachability, i.e., the |
632 // number of nodes in N2 which are not yet covered by at |
676 // number of nodes in N2 which are not yet covered by at |
633 // least one node in the MPR set, and which are reachable |
677 // least one node in the MPR set, and which are reachable |
634 // through this 1-hop neighbor |
678 // through this 1-hop neighbor |
635 std::map<int, std::vector<const NeighborTuple *> > reachability; |
679 std::map<int, std::vector<const NeighborTuple *> > reachability; |