In application cases where millimeter-sized (≤ 5mm diameter) sensor motes are inevitable to gather environmental data, the motes' inherent energy constraints require a radical change in the communication procedure. For application cases like the surveying of hardly permeable underground structures, as they exist e.g. in mining areas of oil sands, ten-thousands of miniature sensors are needed to examine e.g. the oil-resource wealth of the area. This combination of extremely resource limited sensor motes and the need to communicate with several ten-thousands of motes requires changes with respect to the normal communication procedure. As reducing the DS-CDMA code length, which is used for the identification of the motes, saves signification amount of energy, we consider the scenario where a localization of sensor motes is required by means of non-relatable distance measurements. The resulting ambiguities in the distance measurements are due to the reassigning of DS-CDMA codes. In this work, we consider the problem of re-enabling the localization, i.e. of resolving the ambiguities due to non-unique identification of the sensor motes, to allow classical localization algorithms to obtain a positioning of the motes. For this problem, which has already been shown to be NP-hard in general, we present an algorithm that is capable of solving this problem optimally in the maximum a posteriori sense. Further, we show that our algorithm offers significant complexity reductions for large problem instances.
['Stephan Schlupkothen', 'Bastian Prasse', 'Gerd Ascheid']
A dynamic programming algorithm for resolving transmit-ambiguities in the localization of WSN