Distributed Cross layered Channel Assignment and Routing for Multi-Hop Wireless Networks
- 주제(키워드) mutli-hop , ad hoc , mesh , channel assignment , routing , wireless , network
- 발행기관 아주대학교
- 지도교수 Young-June Choi
- 발행년도 2017
- 학위수여년월 2017. 2
- 학위명 박사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000024564
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
As in public safety, military communication or last mile Internet access, multi-hop wireless networks (MWNs) are increasingly becoming an integrated part of the next generation of wireless communication. MWNs can be of flat architecture similar to ad-hoc networks or hierarchical architecture such as mesh and sensor networks. However, devices in MWNs operate on a single channel and interface to stay connected, which degrades the performance of the network due to interference and collision. The reduction of cost and size in radios enables to fit more than one radio per devices. This enables simultaneous transmissions on orthogonal channels, such that the performance of MWNs is multiplied. Even with multiple radios, the absence of infrastructure in MWNs could render the network disconnected, unless devices share a channel in such a way that congestion and interference are avoided. Channel assignment (CA), which is handled at MAC layer, is responsible for creating a connected network. In addition, CA needs to handle the occasional jamming attack from harmful devices and incompatible standards. However, CA decisions result in topology changes that in turn affect routing decisions. This strong interrelationship between these layers require a cross layered approach that provides a reliable connectivity, thus causing network performance enhancement. On the other hand, the multi-hop nature of the architectures, the similarity in choice of standard and the possibility of a device to take part in any of the architectures demands a versatile solution that adapts to any given MWN. In the first part of this dissertation, we formulate the channel assignment problem as graph partitioning problem that minimizes the number of adjacent vertices on the same partition, and then propose a distributed and heuristic channel assignment algorithm called Channel Assignment and JAmmer Mitigation (CA-JAM), because the problem is found to be non-deterministic polynomial-time hard (NP-hard). In CA-JAM, devices are allowed to share channel with limited number of neighbors per interface. To avoid interference, stations look up the number of neighbors per interface and check whether it has multiple links with all neighbors on this interface. If these conditions are satisfied, the station switches to another channel to organize a less congested network and seek more connectivity. The second part of this dissertation, formulates multi-purpose cross-layer problem as network-path cost optimization. Due to the NP-hardness of such problems, we propose a distributed heuristic channel assignment and routing scheme which is applicable to both flat as well as hierarchical multi-hop wireless networks (MWNs) and even resistant to jamming attacks. In distributed jamming resilient channel assignment and routing (DJ-CAR) devices are allowed to share channel with neighbors that can form strong link with. To evaluate the quality of the link by operating on that channel, devices use number of neighbors, signal strength and neighbor's capacity. We use the OPNET simulator to conduct a rigorous simulation experiments and confirm that the performance of the proposed scheme outperforms existing schemes.
more목차
Acknowledgements . . . . . . . . . . . . . . .. . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . iv
Chapter 1 Introduction . . . . . . . . . . . . . .. . . 1
1.1 Background . . . . . . . . . . . . . . . . . . . . 5
1.2 Motivation . . . . . . . . . . . . . . . . .. . . . 12
1.3 Research Organization . . . . . . . . . . . . . . . 13
Chapter 2 Channel Assignment F-WMN . . . . . . . . . . .14
2.1 Problem Definition . . . . . . . . . . . . . . . . 16
2.1.1 Conflict Graph . . . . . . . . . . . . . . . .. . 16
2.1.2 Optimization Problem . . . . . . . . . . . . . .. 18
2.2 CA-JAM Algorithm . . . . . . . . . . . . . . . . . 21
2.2.1 Rendezvous . . . . . . . . . . . . . . . . . . . 24
2.2.2 Interference Avoidance . . . . . . . . . . . .. . 26
2.2.3 Jammer Mitigation . . . . . . . . . . . . . . . . 29
2.2.4 Example of CA-JAM Algorithm . . . . . . . . . . . 31
2.3 Simulation Framework . . . . . . . . . . . . . . . 36
2.4 Performance Evaluation . . . . . . . . . . .. . . . 37
2.5 Summary . . . . . . . . . . . . . . . . . .. . . . 49
Chapter 3 Channel Assignment And Routing MWN. . .. . . 50
3.1 Problem Formulation . . . . . . . .. .. . . . . . . 51
3.1.1 Constraints . . . . . . . . . . . .. . .. . . . . 52
3.1.2 Channel Assignment Sub-problem . .. . . . . . . . 55
3.1.3 Routing Cost Optimization Problem . . . . . . . . 57
3.2 Distributed Heuristic Scheme . . . .. . . . . . . . 60
3.2.1 Network Discovery . . . . . .. . . . . . . . . . 60
3.2.2 Utilization Based CA . . . . . . . . . . . . . . 63
3.2.3 Jammer Resilience . . . . ... . . . . . . . . . . 65
3.2.4 Path Selection . . . . . . . . . . . . . . . . . 66
3.3 Performance Evaluation . . . . . . . . . . . . . . 68
Chapter 4 Conclusion . . . . . . . . . . . . . . . . . 78
Bibliography . . . . . . . . . . . . . . . . . . . . . 79
Appendices . . . . . . . . . . . .. . . . . . . . . . . 88
Appendix A List of Publications . . . . . . . . . . . . 88
