Understanding and solving flip-ambiguity in network localization via semidefinite programming

We employ the semidefine programming (SDP) framework to first analyze, and then solve, the problem of flipambiguity afflicting range-based network localization algorithms with incomplete ranging information. First, we study the occurrence of flip-ambiguous nodes and errors due to flip ambiguity by considering random network topologies with successively smaller connectivity ranges and employing an SDP-based unique localizability test to detect the limiting connectivity ranges RU and RL that are respectively sufficient and un-sufficient to ensure unique localizability. Then, we utilize this information to construct an SDP formulation of the localization problem with Genie-aided constraints, which is shown to resolve flip-ambiguities. Finally, we derive a flipambiguity- robust network localization algorithm by relaxing the Genie-aided constraints onto feasible alternatives. Finally, the performance of the so-obtained localization algorithm is studied by Monte-Carlo simulations, which reveal a substantial improvement over the conventional SDP-based algorithm.