An efficient placement and routing technique for fault-tolerant distributed embedded computing

ABSTRACT

This article presents an efficient technique for placement and routing of sensors/actuators and processing units in a grid network. The driver application that we present is a medical jacket, which requires an extremely high level of robustness and fault tolerance. The power consumption of such jacket is another key technological constraint. Our proposed interconnection network is a mesh of wires. A jacket made of fabric and wires would be susceptible to accidental damage via tears. By modeling the tears, we evaluate the probability of having failures on every segment of wires in our mesh interconnection network. Then, we study two problems of placement and routing in the sensor networks such that the fault tolerance is maximized while the power consumption is minimized. We develop efficient integer linear programming (ILP) formulations to address these problems and perform both placement and routing, simultaneously. This ensures that the solution is a lower bound for both problems. We evaluate the effectiveness of our proposed techniques on a variety of benchmarks.

REFERENCES

• 1: Guillermo Barrenechea , Baltasar Beferull-Lozano , Martin Vetterli, Lattice sensor networks: capacity limits, optimal routing and robustness to failures, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984650]
• 2: Bona, M. 1994. Textile Quality. Texilia, Manchester, UK.
• 3: Burstein, M. and Pelavin, R. 1983. Hierarchical wire routing. IEEE Trans. Comput. Aid. Des. Integr. Circ. Syst. 2, 4, 223--234.
• 4: Andrew E. Caldwell , Hyun-Jin Choi , Andrew B. Kahng , Stefanus Mantik , Miodrag Potkonjak , Gang Qu , Jennifer L. Wong, Effective iterative techniques for fingerprinting design IP, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, p.843-848, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310083]
• 5: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Dunlop, A. E. and Kernighan, B. W. 1985. A Procedure for Placement of Standard Cell VLSI Circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. 4, 1, 92--98.
• 7: Hall, K. 1970. An r-dimensional quadratic placement algorithm. Manage. Sci. 17, 3, 219--229.
• 8: Jung-Chun Kao , Radu Marculescu, Energy-Aware Routing for E-Textile Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.184-189, March 07-11, 2005 [doi>10.1109/DATE.2005.138]
• 9: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual Design Automation Conference, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 10: Kleinhans, J. M., Sigl, G., Johannes, F. M., and Antreich, K. J. 1991. Gordon: Vlsi Placement by quadratic programming and slicing optimization. IEEE Trans. Comput.-Aid. Des. Integr. Circ. 10, 3, 365.
• 11: Lee, J. 1961. An algorithm for path connection and its application. IEEE Trans. Electron. Comput. EC-10, 3, 346--365.
• 12: Meoli, D. and May-Plumlee, T. 2002. Interactive electronic textile development: A review of technologies. J. Textile Apparel Tech. Manage. 2, 2, 1--12.
• 13: N. Lek, R. T. and Kang, S. 1992. A new global router using zero-one integer linear programming techniques for sea-of-gates and custom logic arrays. IEEE Trans. Comput.-Aid Des. Integr. Circ. Syst. 11, 12, 1479--1494.
• 14: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 15: Primentas, A. 2001. Puncture and tear of woven fabrics. J. Textile Apparel Tech. Manage. 1, 4, 1--8.
• 16: Quinn, N. and Breuer, M. 1979. A force directed component placement procedure for printed circuit boards. IEEE Trans. Circ. Syst. 26, 6, 377--388.
• 17: Majid Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
• 18: Shahookar, K. and Mazumder, P. 1990. A genetic approach to standard cell placement using meta-genetic parameter optimization. IEEE Trans. Comput.-Aid. Des. Integr. Circ. 9, 5, 500--511.
• 19: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 20: E. Shragowitz , S. Keel, A global router based on a multicommodity flow model, Integration, the VLSI Journal, v.5 n.1, p.3-16, March 1987 [doi>10.1016/S0167-9260(87)80003-2]
• 21: Phillip Stanley-Marbell , Diana Marculescu , Radu Marculescu , Pradeep K. Khosla, Modeling, Analysis, and Self-Management of Electronic Textiles, IEEE Transactions on Computers, v.52 n.8, p.996-1010, August 2003 [doi>10.1109/TC.2003.1223635]
• 22: Sun, W. J. and Sechen, C. 1995. Efficient and effective placement for very large circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. 14, 3, 349--359.
• 23: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 24: Witkowska, B. and Frydrych, I. 2004. A comparative analysis of tear strength methods. Fibres and Textiles in Eastern Europe 12, 2, 42--47.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Management, Performance, Reliability

Keywords:
Distributed embedded system, fault tolerance, placement, routing, sensor networks