Skip to main content
SpringerLink
Log in

Optimal placement of stereo sensors

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Autonomous wireless devices such as sensor nodes and stereo cameras, due to their low cost of operation coupled with the potential for remote deployment, have found a plethora of applications ranging from monitoring air, soil and water to seismic detection and military surveillance. Typically, such a network spans a region of interest with the individual nodes cooperating to detect events and disseminate information. Given a deployment of sensors and targets over a region, a sensor pairing is desired for each target that optimizes the coverage under certain constraints. This problem can be modeled as an integer programming problem and solved using branch-and-cut. For larger problems, it is necessary to limit the number of variables, and a GRASP routine was developed for this purpose. Valid cutting planes are developed and computational results presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aiex R.M., Pardalos P.M., Resende M.G.C. and Toraldo G. (2005). GRASP with path-relinking for three-index assignment. INFORMS J. Comput. 17(2): 224–247

    Article  MathSciNet  Google Scholar 

  2. Akyildiz I.F., Su W., Sankarasubramaniam Y. and Cayirci E. (2002). A survey on sensor networks. IEEE Commun. Mag. 40(8): 102–114

    Article  Google Scholar 

  3. Bredin, J.L., Demaine, E.D., Hajiaghayi, M.T., Rus, D.: Deploying sensor networks with guaranteed capacity and fault tolerance. In: Proceedings of the 6th ACM International Symposium on Mobile ad hoc Networking and Computing MobiHoc ’05, pp. 309–319 (2005)

  4. Chvátal V. (1973). Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4: 305–337

    Article  MATH  MathSciNet  Google Scholar 

  5. Edmonds J. (1965). Maximum matching and a polyhedron with 0, 1 vertices. J. Res Nat Bureau Stand. 69: 125–130

    MATH  MathSciNet  Google Scholar 

  6. Feo T.A. and Resende M.G.C. (1995). Greedy randomized adaptive search procedures. J. Global Optim. 6: 109–133

    Article  MATH  MathSciNet  Google Scholar 

  7. Grundel D., Oliveira C.A.S. and Pardalos P.M. (2004). Asymptotic properties of random multidimensional assignment problems. J. Optim. Theory Appl. 122(3): 487–500

    Article  MATH  MathSciNet  Google Scholar 

  8. Isler V., Khanna S., Spletzer J. and Taylor C.J. (2005). Target tracking with distributed sensors: the focus of attention problem. Comput. Vis Image Understand. J. 100(1-2): 225–247

    Article  Google Scholar 

  9. Johnsson M., Magyar G. and Nevalainen O. (1998). On the Euclidean 3-matching problem. Nordic J. Comput. 5(2): 143–171

    MATH  MathSciNet  Google Scholar 

  10. Li, Y., Pardalos, P.M., Resende, M.G.C.: A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos, P. M., Wolkowicz, H. (eds.) Quadratic assignment and related problems, vol. 16 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 237–261. American Mathematical Society (1994)

  11. Lloyd, E.L., Liu, R., Marathe, M.V., Ramanathan, R., Ravi, S.S.: Algorithmic aspects of topology control problems for ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking and Computing, pp. 123–134 (2002)

  12. Pitsoulis L.S. and Resende M.G.C. (2002). Greedy randomized adaptive search procedures. In: Pardalos, P.M. and Resende, M.G.C. (eds) Handbook of Applied Optimization, pp 168–183. Oxford University Press, Oxford

    Google Scholar 

  13. Rentala P., Musunuri R., Gandham S., Saxena U. (2003) Survey of sensor networks. Technical Report UTDCS-10-03, Department of Computer Science. University of Texas at Dallas, Richardson

  14. Resende M.G.C. and Ribeiro C.C. (2002). Greedy radomized adaptive search procedures. In: Glover, F. and Kochenberger, G. (eds) Handbook of Metaheuristics, pp 219–249. Kluwer, Dordrecht

    Google Scholar 

  15. Resende M.G.C and Ribeiro C.C. (2005). GRASP with path relinking: recent advances and applications. In: Ibaraki, T., Nonobe, K. and Yagiura, M. (eds) Metaheuristics: Progress as Real Problem Solvers, pp 301–331. Springer, Berlin

    Google Scholar 

  16. Tilak S., Abu-Ghazaleh N. and Heinzelman W. (2002). A taxonomy of wireless micro-sensor network models. ACM Mobile Comput. Commun. Rev. (MC2R) 6(2): 28–36

    Article  Google Scholar 

  17. Tubaishat M. and Madria S. (2003). Sensor networks: an overview. IEEE Potent. 22(2): 20–23

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rensselaer Polytechnic Institute Troy, Troy, NY, 12180, USA

    Mohammad Al Hasan

  2. Department of Electrical, Rensselaer Polytechnic Institute Troy, Troy, NY, 12180, USA

    Krishna K. Ramachandran

  3. Department of Mathematical Sciences, Rensselaer Polytechnic Institute Troy, Troy, NY, 12180, USA

    John E. Mitchell

Authors
  1. Mohammad Al Hasan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Krishna K. Ramachandran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. John E. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to John E. Mitchell.

Additional information

Research supported in part by NSF grant numbers DMS–0317323 and CMS–0301661.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Al Hasan, M., Ramachandran, K.K. & Mitchell, J.E. Optimal placement of stereo sensors. Optimization Letters 2, 99–111 (2008). https://doi.org/10.1007/s11590-007-0046-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-007-0046-5

Keywords

Search

Navigation