NPART - node placement algorithm for realistic topologies in wireless multihop network simulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

NPART - node placement algorithm for realistic topologies in wireless multihop network simulation

Full text

Pdf (807 KB)

Source

International Conference On Simulation Tools And Techniques For Communications, Networks And Systems & Workshops archive
Proceedings of the 2nd International Conference on Simulation Tools and Techniques table of contents

Rome, Italy

SESSION: Wireless mesh networks table of contents

Article No. 9

Year of Publication: 2009

ISBN:978-963-9799-45-5

Authors

Bratislav Milic	Humboldt University, Berlin
Miroslaw Malek	Humboldt University, Berlin

Sponsors

: Create-Net
: ICST

Publisher

ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) ICST, Brussels, Belgium, Belgium

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 19, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.4108/ICST.SIMUTOOLS2009.5669

ABSTRACT

Despite a considerable number of topology generation algorithms for simulation of wireless multihop networks it is difficult to find one with output similar to real networks.

We propose NPART --- a Node Placement Algorithm for Realistic Topologies whose output topologies resemble networks encountered in reality. The algorithm is flexible since it is sufficient to provide it with different input data to obtain different topologies. To demonstrate its quality, we compare topologies generated by NPART algorithm with our measurements from open wireless multihop networks in Berlin and Leipzig. Compared with real topologies, the generated topologies have almost identical node degree distribution, similar number of cut-edges and vertices, and distribution of component sizes after bridge removal.

The importance of node placement algorithm is demonstrated by comparing ns-2 simulation results for grid and uniform node placement with NPART generated topologies. Simulation results show that node placement model plays as important role in simulation outcome as the accuracy of wireless signal propagation model.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Aguiar and J. Gross. Wireless Channel Models. Technical Report TKN-03-007, TU Berlin, 2003.
	2	Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
	3	Christian Bettstetter , Michael Gyarmati , Udo Schilcher, An inhomogeneous spatial node distribution and its stochastic properties, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece [doi>10.1145/1298126.1298195]
	4	K. Fall and K. Varadhan. The ns2 manual. September, 2008. http://www.isi.edu/nsnam/ns/ns-documentation.html.
	5	L. Fang, W. Du, and P. Ning. A beacon-less location discovery scheme for wireless sensor networks. In In Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005.
	6	M. Gudmundson. Correlation model for shadow fading in mobile radio systems. Electronic Letters, 27:2145--2146, 1991.
	7	E. Krause. Taxicab Geometry: An Adventure in Non-Euclidean Geometry. Dover, New York, 1986.
	8	Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778431]
	9	Xiaowen Liu , Martin Haenggi, Toward Quasiregular Sensor Networks: Topology Control Algorithms for Improved Energy Efficiency, IEEE Transactions on Parallel and Distributed Systems, v.17 n.9, p.975-986, September 2006 [doi>10.1109/TPDS.2006.130]
	10	Bratislav Milic , Miroslaw Malek, Adaptation of the breadth first search algorithm for cut-edge detection in wireless multihop networks, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece [doi>10.1145/1298126.1298192]
	11	B. Milic and M. Malek. Analyzing large scale real-world wireless multihop network. IEEE Communication Letters, 11:580--582, 2007.
	12	B. Milic and M. Malek. NPART - Node Placement Algorithm for Realistic Topologies in Wireless Multihop Network Simulation. Technical Report 224, HU Berlin, 2008.
	13	B. Milic and M. Malek. to appear in: Handbook of Wirless Ad Hoc and Sensor Networks, chapter Properties of Wireless Multihop Networks in Theory and Practice. SpringerVerlag, 2009.
	14	John Mullen , Hong Huang, Impact of multipath fading in wireless ad hoc networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089803.1089984]
	15	M. Newman, S. Strogatz, and D. Watts. Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64, 2001.
	16	E. C. H. Ngai, Y. Zhou, M. R. Lyu, and J. Liu. Reliable reporting of delay-sensitive events in wireless sensor-actuator networks. In Proceedings of The Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Vancouver, Canada, 2006.
	17	F. A. Onat and I. Stojmenovic. Generating random graphs for wireless actuator networks. In Proceedings of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM, 2007.
	18	C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
	19	R. J. Punnoose, P. V. Nikitin, and D. D. Stancil. Efficient simulation of ricean fading within a packet simulator. In Proceedings of the Vehicular Technology Conference, 2000.
	20	Mineo Takai , Jay Martin , Rajive Bagrodia, Effects of wireless physical layer modeling in mobile ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501429]
	21	N. Vicari. Models of WWW-Traffic: a Comparison of Pareto and Logarithmic Histogram Models. Technical Report 198, Institute of Computer Science, University of Wuerzburg, 1998.
	22	D. B. West. Introduction to Graph Theory. Prentice Hall, 1996.
	23	Yiwei Wu , Yingshu Li, Construction algorithms for k-connected m-dominating sets in wireless sensor networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374631]
	24	S. Zhu, W. Wang, and C. V. Ravishankar. A new power-efficient scheme to deliver time-sensitive data in sensor networks. In Proceedings of The Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Vancouver, Canada, 2006.