Home » Posts tagged 'ad hoc network'
Tag Archives: ad hoc network
- Force-directed algorithms for schematic drawings and placement: A survey
- Snapshot Visualization of Complex Graphs with Force-directed Algorithms
- CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks
- Design and Implementation of Lifeline Emergency Ad Hoc Network
- Architecture of Force-directed Algorithms
Efficient message forwarding in mobile ad hoc network in disaster scenarios is challenging because location information on the boundary and interior nodes is often unavailable. Information related to boundary nodes can be used to design efficient routing protocols as well as to prolong the battery power of devices along the boundary of an ad hoc network. In this article, we developed an algorithm, CWBound, which discovers boundary nodes in a complex non-convex mobile ad hoc (CNCAH) networks.
Experiments show that the CWBound algorithm is at least 3 times faster than other state-of-the-art algorithms, and up to 400 times faster than classical force-directed algorithms. The experiments also confirmed that the CWBound algorithm achieved the highest accuracy (above 97% for 3 out of the 4 types of CNCAH networks) and sensitivity (90%) among the algorithms evaluated.
The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/CWBound.pdf. Se-Hang, Cheong, and Yain-Whar Si. "CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks." The Journal of Supercomputing (2018): 1-20.
However, Public Switched Telephone Networks (PSTN), including cellular networks could be disrupted during natural disasters, such as earthquakes, hurricane, tsunami, etc.
In such situations, mobile phone users may not be able make emergency calls since cellular signal is likely to be unavailable due to the destruction of land-based network infrastructures. Although we cannot assume that all people trapped under debris will have access to their mobile phones, it is possible that some of them may still have access to their mobile phones when they are trapped under the debris or when they are waiting to be rescued.
This paper proposes a system for automatically forming ad hoc networks using mobile phones and battery-powered wireless routers for emergency situations. The system also provides functions to send emergency messages and identify the location of victims based on the network topology information.
The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/Saving-Lives：Design-and-Implementation-of-Lifeline-Emergency-Ad-Hoc-Network.pdf. Se-Hang Cheong, Yain-Whar Si, Leong-Hou U. “Saving Lives: Design and Implementation of Lifeline Emergency Ad Hoc Network”, International Journal of Pervasive Computing and Communications, Accepted and to appear.
CNCAHNetGenerator is written in Java 7, to enable the creation of CNCAH networks of arbitrary node and edge types.
If you use CNCAH Network Generator for your research/development, please cite the following paper: Cheong, S.-H., Si, Y.-W., 2016. Accelerating the kamada-kawai algorithm for boundary detection in a mobile ad hoc network. ACM Transactions on Sensor Networks (TOSN) 13 (1), 3. Download EndNote Format (.enw), Download BibteX Format (.bib)
License & disclaimer
- CNCAHNetGenerator is freeware and under the LGPL License.
- You may not modify, reverse engineer, decompile, or disassemble the object code portions of this software.
- This software is provided “as is” and without any warranties expressed or implied, including, but not limited to, implied warranties of fitness for a particular purpose, and non-infringement. You expressly acknowledge and agree that use of the Software is at your sole risk.
- In no event shall the author be liable for any damages whatsoever (including, without limitation, damages for loss of business profits, business interruption, loss of business information, or other pecuniary loss) arising out of the use of or inability to use this software or documentation, even if the author has been advised of the possibility of such damages.
Current: CNCAHNetGenerator version 0.1, from September 14, 2017.
- CNCAHNetGenerator can generate CNCAH networks via the command line or the graphical interface. Example commands are shown in follows:
java -jar CNCAHNetGenerator.jar -help java -jar CNCAHNetGenerator.jar -n -v 1000 -e 4000 -o star -sf shapes\star.shape java -jar CNCAHNetGenerator.jar -n -v 1000 -e 4000 -o donut -sf shapes\donut.shape java -jar CNCAHNetGenerator.jar -n -v 1000 -e 4000 -o smile -sf shapes\smile.shape java -jar CNCAHNetGenerator.jar -n -v 1000 -e 4000 -o ushape -sf shapes\ushape.shape
Complex non-convex ad hoc networks (CNCAH) contain intersecting polygons and edges. In many instances, the layouts of these networks are also not entirely convex in shape. In this paper, we propose a Kamada-Kawai based algorithm called W-KK-MS for boundary node detection problem, which is capable of aligning node positions while achieving high sensitivity, specificity and accuracy in producing a visual drawing from the input network topology. The algorithm put forward in this paper selects and assigns weights to top-k nodes in each iteration in order to speed up the updating process of nodes. We also propose a novel approach to detect and unfold stacked regions in CNCAH networks. Experimental results show that the proposed algorithms can achieve fast convergence on boundary node detection in CNCAH networks and are able to successfully unfold stacked regions. The design and implementation of a prototype system called ELnet for analyzing CNCAH networks is also described in this paper. The ELnet system is capable of generating synthetic networks for testing, integrating with force-directed algorithms, and visualizing and analyzing of algorithms’ outcomes.
The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/Boundary-node-detection-and-unfolding-of-complex-non-convex-ad-hoc-networks.pdf. Se-Hang Cheong, and Yain-Whar Si. "Boundary node detection and unfolding of complex non-convex ad hoc networks" ACM Transactions on Sensor Networks (TOSN) 14.1 (2017): 1.
Force-directed algorithms such as the Kamada-Kawai algorithm have shown promising results for solving the boundary detection problem in a mobile ad hoc network. However, the classical Kamada-Kawai algorithm does not scale well when it is used in networks with large numbers of nodes. It also produces poor results in non-convex networks. To address these problems, this paper proposes an improved version of the Kamada-Kawai algorithm. The proposed extension includes novel heuristics and algorithms that achieve a faster energy level reduction. Our experimental results show that the improved algorithm can significantly shorten the processing time and detect boundary nodes with an acceptable level of accuracy.
The author’s version of a work that was accepted for publication can be downloaded from Accelerating Kamada-Kawai for boundary detection in Mobile Ad-Hoc network. Se-Hang Cheong, and Yain-Whar Si. "Accelerating the Kamada-Kawai algorithm for boundary detection in a mobile ad hoc network." ACM Transactions on Sensor Networks (TOSN) 13.1 (2016): 3.
Lifeline is a group of systems designed for mobile phones and battery powered wireless routers for forming emergency Ad hoc networks.
Devices installed with Lifeline program can automatically form Ad hoc networks when cellular signal is unavailable or disrupted during natural disasters. For instance, large scale earthquakes can cause extensive damages to land-based telecommunication infrastructures. In such circumstances, mobile phones installed with Lifeline program can be used to send emergency messages by the victims who are trapped under collapsed buildings. In addition, Lifeline also provides a function for the rescuers to estimate the positions of the victims based on network propagation techniques. Lifeline also has the ability to recover from partial crash of network and nodes lost.
The details and implementation are described in this paper: Se-Hang Cheong, Kai-Ip Lee, and Yain-Whar Si. "Lifeline: emergency ad hoc network." In Computational Intelligence and Security (CIS), 2011 Seventh International Conference on, pp. 283-289. IEEE, 2011. The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/lifeline.pdf.
Constructing an emergency network based on portable devices that forward emergency messages to the emergency stations or rescue teams could be helpful in disaster scenarios. No central server is needed because portable devices are self-organized in the ad hoc network.
The basic idea to build such emergency network is shown as follows:
- Compile the source code of OLSR (Optimized Link State Routing Protocol) and install them into the Android Operating System and wireless routers.
- Each portable device is designed to store the neighbor’s information so as to allow recovery from partial crash.
- Through the integration of OLSR with the Android, messages are allowed to be forwarded in the emergency network by the portable devices.