A Model of an Amorphous Computer and Its Communication Protocol
作者： Lukáš Petrů , Jiří Wiedermann
DOI: 10.1007/978-3-540-69507-3_38
关键词:
摘要: We design a formal model of an amorphous computer suitable for theoretical investigation its computational properties. The consists finite set nodes created by RAMs with restricted memory, which are dispersed uniformly in given area. Within limited radius the can communicate their neighbors via single-channel radio. assumptions on low-level communication abilities among weakest possible: work asynchronously, there is no broadcasting collision detection mechanism and network addresses. For underlying we randomized protocol analyze efficiency. subsequent experiments combinatorial analysis random networks show that expectations under our was designed met vast majority instances model.
springer.com
researchgate.net 
sci-hub.st 参考文章(16)
Paul G. Spirakis, Algorithmic and foundational aspects of sensor systems: (Invited talk) algorithmic aspects of wireless sensor networks. pp. 3- 8 ,(2004)
Paul G. Spirakis, Algorithmic and Foundational Aspects of Sensor Systems Algorithmic Aspects of Wireless Sensor Networks. pp. 3- 8 ,(2004) , 10.1007/978-3-540-27820-7_2
Sotiris Nikoletseas, Models and algorithms for wireless sensor networks (smart dust) conference on current trends in theory and practice of informatics. pp. 64- 83 ,(2006) , 10.1007/11611257_7
Robert B. Ellis, Jeremy L. Martin, Catherine Yan, Random Geometric Graph Diameter in the Unit Disk with ℓ p Metric Graph Drawing. pp. 167- 172 ,(2005) , 10.1007/978-3-540-31843-9_18
Harold Abelson, Don Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas F. Knight, Radhika Nagpal, Erik Rauch, Gerald Jay Sussman, Ron Weiss, Amorphous computing Communications of The ACM. ,vol. 43, pp. 74- 82 ,(2000) , 10.1145/332833.332842
Piyush Gupta, P. R. Kumar, Critical Power for Asymptotic Connectivity in Wireless Networks Birkhäuser, Boston, MA. pp. 547- 566 ,(1999) , 10.1007/978-1-4612-1784-8_33
Brett Warneke, Matt Last, B. Liebowitz, Kristofer SJ Pister, Smart Dust: communicating with a cubic-millimeter computer IEEE Computer. ,vol. 34, pp. 44- 51 ,(2001) , 10.1109/2.963443
Ingmar Glauche, Wolfram Krause, Rudolf Sollacher, Martin Greiner, Continuum percolation of wireless ad hoc communication networks Physica A: Statistical Mechanics and its Applications. ,vol. 325, pp. 577- 600 ,(2003) , 10.1016/S0378-4371(03)00249-8
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization Journal of Computer and System Sciences. ,vol. 45, pp. 104- 126 ,(1992) , 10.1016/0022-0000(92)90042-H
Pascal Fradet, Jean-Pierre Banâtre, Jean-Louis Giavitto, Olivier Michel, Unconventional Programming Paradigms ,(2008)