NPART - Tool for Realistic Topologies in WMN Simulation
A novel topology generator for simulation of Wireless Mesh Networks
There exists a number of topology generation algorithms for simulation of wireless mesh networks. In [1] and [2] we have shown that the existing node placement models create topologies that are considerably different than topologies of real networks. In order to correct this issue we have developed novel node placement algorithm - NPART that creates topologies that resemble the real topologies.
The algorithm is:
- Realistic: if algorithm receives input based on measurements from a real network, the topologies that it produces should have similar properties as the original networks.
- Random - the algorithm does not merely re-create a sampled topology from measured node locations, wireless device parameters (power, receiving threshold), signal to noise ratio. It is capable to create new, random topologies but preserving the properties of adaptivity and reality.
Up to our best knowledge, this is the first node placement algorithm for wireless mesh networks that creates topologies that have properties similar to real world networks' properties.
NPART implementation and sample topologies can be downloaded at the bottom of this page.
Comparison of topological properties: NPART vs. Uniform node placement
To demonstrate realistic nature of NPART topologies, we compare NPART topologies with topology samples from open wireless mesh networks in Berlin.
Compared to the 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.
Figure 1. Topologies created by the uniform placement model
Figure 2. A topology from Berlin's wireless network (Freifunk Berlin)
and a topology produced by NPART
Figures 1 and 2 visually illustrate the differences between common uniform node placement model, real topology shape and topologies produced by our algorithm.
Figure 3 shows almost ideal fit between real degree distributions and distributions of topologies produced by our algorithm.
Figure 4. Cummulative distribution of bridge-to-edge ratio
Finally, Figure 4 shows the difference in number of cut edges that are produced by uniform, our topology generator and real topologies. As it can be seen, uniform placement model creates less than 1% of cut edges, while real topologies have close to 10% of cut edges.
Again, topologies produced by the new generator follow closely the properties of real topologies.
Download of NPART tool implementation
Java classes that implement NPART can be downloaded from
NPART download
Just unzip it and start the runNpart.bat file.
The following external library is included in the zip file (it is required for algorithm's operation):
mantissa
The ns2 topologies produced by NPART may be used by the Jist/SWANS simulator if you add the jist.swans.field.Placement.NPART class to it. Instructions on its use are embedded in the downloaded file.
Finally, please note that you are using NPART and Jist/SWANS code on your own risk and the author and HU Berlin are not liable for possible damage/issues with it.
Of course, we will do our best to help you with its use and attempt to correct obseved bugs with it as soon as possible.
If you have issues running the tool, please contact the author.
|
|
|
Figure 5. Tool screenshot and configuration dialog
Download of Exemplary Topologies
It is also possible to download two sets of topologies for ns2 simulator created by NPART.
The topologies that resemble Berlin's mesh network consist of 275 nodes and topologies similar to Leipzig's network have 346 nodes.
NPART/Berlin download
NPART/Leipzig download
Note: In their creation it is assumed the default ns2 communication range and path loss model. For realistic simulation results, shadowing and fading propagation models must be added to the simulation.
References:
[1] Analyzing Large Scale Real-World Wireless Multihop Network
Milic B. and Malek M.
in: IEEE Communication Letters, July 2007
[2] Properties of wireless multihop networks in theory and practice
Milic B., Malek M.
book chapter in: Guide to Wirless Ad Hoc Networks, S. Misra, I.Woungang, S. Misra (Eds.), Springer Verlag, 2009
[3] NPART - Node Placement Algorithm for Realistic Topologies in Wireless Multihop Network Simulation,
Milic Bratislav, Malek Miroslaw,
in Proceedings of the Second International Conference on Simulation Tools and Techniques (SIMUTools 2009)
