Understanding and Solving Flip-Ambiguity in Network Localization via Semidefinite Programming

We employ the semidefinite programming (SDP) framework to first analyze, and then solve, the problem of flip-ambiguity 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 R_Max > R_Max - ¿R > ¿ > R_U > R_L, and employing an SDP-based unique localizability test to detect the limiting connectivity ranges R_U and R_L 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 flip-ambiguity-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.