Hierarchical Topology Control for Wireless Networks

Theory, Algorithms, and Simulation

Jiguo Yu, Cheng Xiuzhen, Jiang Honglu, Dongxiao Yu

• Publisher: CRC Press
• Year: 2018
• Print ISBN: 9780367572174
• eBook ISBN: 9781351645546
• Edition: 1
• Topic: Computer Science
• Subtopic: Information Technology
• Index: Computer Science

First Published in 2018. This book covers the concepts of architecture and applications on wireless ad hoc networks and wireless sensor networks, including topology control, the clustering algorithm in topology control, and virtual backbone construction algorithms, focusing on connected dominating set construction, including various transformations for dominating sets.

Chapter 1

Wireless Networks

1.1 Introduction

1.1.1 Introduction to Wireless Networks

The wireless network includes global voice and data networks that allow users to establish long-range wireless connections, as well as infrared and radio frequency (RF) technologies optimized for short-range wireless communication. The uses of wireless and wired networks are very similar. The biggest difference between wireless networks and wired networks is in the different transmission media. Wireless networks use radio technology instead of network cable, but the wireless network can be a backup for wired networks.

A wireless network is designed to construct a ubiquitous computing environment that truly realizes 6As: anyone can use a wireless network at any time, at any location by any means with any other person for anything. Wireless network technology is the core technology for achieving the 6As dream—mobile computing and ubiquitous computing (Figure 1.1).

1.1.1.1 Development History of Wireless Networks

The origins of wireless networks can be traced back to World War II, when the US Army used radio signals to transmit data. The Army developed a set of radio transmission technologies, using encryption technology with high intensity, which was widely used in both the US military and the allied military. In 1971, researchers at the University of Hawaii created the first radio communication network based on the packet technology. This is called the ALOHAnet, also known as the ALOHA system or simply ALOHA; it was a pioneering computer networking system developed at the University of Hawaii. ALOHA originally stood for Additive Links On-line Hawaii Area. Generally, we call it ALOHAnet directly.

Figure 1.1 A canonical wireless network.

The ALOHAnet can be regarded as the wireless local area network (WLAN) of the early stage. It includes seven computers that use a bidirectional star topology across four Hawaiian Islands, while the central computer is put on the Oahu Island. From that point, the wireless network can be said to be officially born.

1. First-generation (1G) mobile communication system
   The simulative cellular mobile communication system was born in the 1970s. The 1G system uses the analog signal transmission mode to achieve voice service, using frequency division multiple access (FDMA) technology to divide the channel.
   Representative: The mobile phone system “Advanced Mobile Phone Service” (AMPS) was first scheduled to commence commercial service in 1983; it was developed by AT&T Bell Labs in the United States in 1976. In the AMPS, the communication area is divided into hexagonal cells, called “One Cell” (10–20 km), with a low-power radio base station, as shown in Figure 1.2. The base station is linked to the mobile telephone switching center and then linked with the local public center network or another mobile telephone switching center, which completes the call link.
   

   Figure 1.2 Hexagonal honey comb.
   The process of making mobile subscriber calls is as follows: the user requests the channel from the base station. The base station assigns the idle channel to the user if there is an idle channel at this time. When the mobile phone in the talking state is handed over, the switching center notifies the new cellular structure to take over this mobile phone and then selects one available channel, so that the call will not be interrupted. When the roaming phenomenon occurs (i.e., a move to another cellular structure that does not belong to the supervision of unified switching center), the new switching center will be responsible for establishing communication connection.
2. Second-generation (2G) mobile communication network
   Since the 1G system has deficiencies such as low spectrum efficiency, poor voice quality, low access capacity, poor security, and no data communication services, it has been replaced by a digital cellular mobile communication system, forming the 2G mobile communication network.
   The 2G mobile communication system currently has two major mobile communication standards: global system for mobile communication (GSM) and code division multiple access (CDMA) system. At present, the mainstream technology of global mobile communication among them is the digital mobile phone system.
   Representative: GSM of digital cellular mobile communication standard and CDMA.
   1. GSM communication
      GSM was jointly developed in 1990 by the European Conference of Postal and Telecommunications Administrations and the European Telecommunications Standards Institute, for which the signal transmission is the same as for traditional wired telephones.
      The GSM system is mainly constituted by the mobile station, the base station subsystem, and the network subsystem. The mobile station may be a portable station or vehicular stations and may be equipped with a terminal equipment or a terminal adapter. The base station subsystem refers to the base transceiver station and the base station controller; the network subsystem refers to the mobile switching center, the operation and maintenance center, the home location registers, visiting location register, an authentication center, and a device flag register.
   2. CDMA system
      CDMA technology has been widely used in military anti-jamming communication research. In November 1989, Qualcomm’s field tests in the United States proved that CDMA has a large capacity for cellular mobile communications, making it a hot topic in the world. In 1995, CDMA public network entered commercial use in Hong Kong and the US. Global CDMA users had reached more than 5 million by 1998 and 20 million by 1999. China’s CDMA development was not behind with its long-term military research and technology accumulation; 863 national programs of CDMA cellular technology research had been carried out by 1993.
      At present, the international common CDMA standard is the IS series of standards mainly developed and promulgated by the American National Standards Institute and the Telecommunications Industry Association. The Telecommunications System Bulletin file, increased to 14.4 kb/s rate group on the basis of IS95A, assigned or switched to the personal conference standard, 1900 MHz, band, and so on.
3. Third-generation (3G) cellular mobile networks
   The International Telecommunications Union (ITU) put forward the third generation (3G) mobile communication prototype as early as 1985. Therefore, the uniform standard and frequency band, improving the spectrum efficiency and supporting multimedia mobile communication, is the main difference between 3G mobile communication and 2G. Broadband Wideband Code Division Multiple Access (WCDMA) proposed in Europe uses the frequency division duplex channel. The supporters of WCDMA are mainly in Europe and Japan, as well as in the GSM network operators and manufacturers. The WCDMA can gradually change over to 3G mobile communication based on the existing GSM via General Packet Radio Service (GPRS). The ITU proposed the concept of the 3G mobile communication system in 1985 and named it the “Future Public Land Mobile Telecommunication System.” In 1996, the ITU changed its name to “International Mobile Telecommunications-2000” (IMT-2000).
   The 3G technology works in 2000 MHz, with a maximum transmission rate of 2000 kbps, which entered commercial use in 2000.
   1. Functions of 3G: To support the broadband digital mobile network with voice data integration and mobile multimedia services. To provide higher capacity and faster data transmission rate and achieve the integration of mobile phones, the Internet, computers, and a variety of household appliances. To provide mobile network, video on demand (VOD), videophone, distance education, and other personalized, global, and multimedia communication services. It constitutes four function subsystems: core network (CN), radio access network (RAN), mobile station (MS), and user identification module, in which the CN and the RAN are the important contents of the 3G mobile communication systems.
   2. Main features of 3G: It integrates the functions of cellular, cordless communication, paging, clustering, wireless spread spectrum, wireless access, mobile data, mobile satellite, personal communication, and other mobile communications. It provides high-quality service compatible with fixed telecommunication networks, supporting for low-rate voice and data services, and asymmetric data transmission. The three major services of mobility, interaction, and distribution can be realized through the connection of global satellite network from micro microcell, to microcell, then to macrocell, until it reaches the point of “anytime, anywhere.”
   3. The main standard of 3G is IMT-2000 CDMA-DS (Direct-Spread Spectrum (DSSS) CDMA technology), WCDMA, which can directly spread the signal within the frequency bandwidth of 5 M, jointly submitted by Europe and Japan; IMT-2000 CDMA-multi-carrier (MC), CDMA2000, was submitted by the US technology companies represented by Qualcomm that a number of 1.25 M narrowband DSSS systems are assembled into a broadband system; IMT-2000 CDMA-time division duplex (TDD), TD-SCDMA, proposed by China Datang Telecom, is the only 3G communication standard approved by ITU based on TDD.
4. Fourth-generation (4G) mobile communication system
   While the world’s major network operators were planning the next-generation network, the Nordic TeliaSonera first completed the 4G (fourth-generation) network construction using Long-Term Evolution (LTE) technology and began to provide 4G service in the Swedish capital, Stockholm, and the Norwegian capital, Oslo, which is the first official commercial 4G network worldwide. The LTE project is the evolution of 3G; it improves and enhances the 3G air access technology, using orthogonal frequency division multiplexing (OFDM) and multiple-input, multiple-output (MIMO) as the only standard of the evolution of wireless networks.
   China Mobile also invested about 180 billion Yuan to start a comprehensive 4G network construction in mid-2012. It includes the equipment procurement for TD-LTE (China’s 4G technical standards) in 100 cities of China in 2013. The size of the completion of TD-LTE base stations is more than 200,000. That is, 180,000 new base stations were constructed in 2013.
   4G mobile communication is the ideal mode for supporting high-speed data (2–20 Mb/s) connection, also known as the broadband access and distribution network, with an asymmetric data transmission capacity of more than 2 Mb/s and an automatic switching capability of different rates from 2 to 100 Mb/s.
   The 4G mobile communication system is a multifunction integrated broadband mobile communication system, which is different from the 3G system in terms of service, function, and frequency band. It provides wireless services in different fixed and wireless platforms and network operation across different frequency bands, which is closer to personal communication than the 3G mobile communication.
   The 4G mobile communication technology can increase the Internet speed to 50 times greater than 3G mobile technology and can achieve three-dimensional image transmission of high quality. The information transmission series of the 4G mobile communication technology is one level higher than the 3G mobile communication technology. The use efficiency of wireless frequency is much higher than that in the 2G and 3G systems, with better anti-signal fading performance. In addition to high-speed information transmission technology, it includes a high-speed mobile wireless information access system, the pull technology of mobile platform, encryption technology, and inter-terminal communication technology with high security. The 4G terminals can also be used for positioning, alarm, and so on.
   The 4G system can automatically manage and dynamically change its structure to meet the system changes and requirements of development. Users may use a variety of mobile devices to access the 4G system. Several different access systems combine into a common platform; the systems can complement each other to meet different business requirements. While mobile network services tend to be diversified, they ultimately will evolve and become a bridge for communication in multiple industries, sectors, and societies.
   Prior to the deployment of 4G communication network systems, most of the global wireless infrastructure was built on the 3G mobile communication system. Many of the world’s wireless infrastructures would have to go through a significant amount of change and updates if they were to migrate to 4G communication technologies. So far, 4G technology has not been universally used, and the 3G technology still has a longer life cycle. The LTE technology is seen as an extension of the 3G technology.

1.1.1.2 Standards for Wireless Networks

The common standards for wireless networks are as follows:

IEEE 802.11a: It uses the 5 GHz frequency band, with the transmission speed of 54 Mbps, and is not compatible with 802.11b.

IEEE 802.11b: It uses the 2.4 GHz frequency band, with the transmission speed of 11 Mbps.

IEEE 802.11g: It uses the 2.4 GHz frequency band, with the transmission speed of 54 Mbps, and is compatible with 802.11b.

IEEE 802.11n draft: It uses the 2.4 GHz frequency band, with the transmission speed of up to 300 Mbps. The current standard is still the draft, but the product has emerged in an endless stream.

IEEE 802.11b is currently the most commonly used, but 802.11g has the ability to be the next generation of IEEE standard. The 802.11n is also in rapid development.

The standard of IEEE 802.11b contains two parts that ensure access c...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Contents
• Preface
• Acknowledgments
• Authors
• 1 Wireless Networks
• 2 Topology Control of Wireless Networks
• 3 Clustering Algorithms
• 4 Dominating Set Theory and Algorithms
• 5 Simulation and Example
• Index