Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph G, to find a minimum set S of vertices in G such that there is a unique minimum vertex cover of G containing S. We show that PAU-VC is fixed parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in polynomial time on split graphs and unit interval graphs.

To deliver services using wireless connectivity on mobile devices, service discovery with low power and service execution with fast connection are the essential factors. However, no single connectivity technology satisfies fast service execution with low power discovery because agile service delivery fundamentally requires consuming high power. Therefore, we propose a synergetic multi-connectivity strategy utilizing Bluetooth Low Energy (BLE) discovery and Wi-Fi Peer to Peer (P2P) fast connection for agile service delivery. Furthermore, we develop an adaptive BLE discovery algorithm to enhance the discovery performance. Finally, the experiment of the multi-connectivity scheme and the theoretical simulation of the discovery algorithm show that the proposed approach excellently provides the fast service delivery with low power discovery.

The dynamic change of wireless channel condition causes poor Wi-Fi quality of service. To cope with the channel variation of wireless communication, the essential strategy for the physical layer with multi-rate capability is the link adaptation. However, because definite guidelines for rate changes do not exist, most link adaptation algorithms can misleadingly increase transmission rates. Therefore, we propose a cognitive link adaptation scheme, sensing link adaptation urgency and responding with differentiated rate control such as the long-term rate adaptation with a short-term rate drop. To evaluate the proposed scheme, we implement the link adaptation scheme on Wi-Fi System-on-Chip, applying the optimal HW/SW partitioning technique to reduce the SW processing delay from heavy operating calculation for the algorithm. The experiment shows that the proposed algorithm increases the packet arrival rate in a real Wi-Fi environment by reducing transmission failure due to wrong rate changes.

ABSTRACT For wireless mobile multihop relay (MMR) networks, we have chosen orthogonal frequency division multiple access (OFDMA) and time division duplex as a multiple access scheme and a duplex communication technique, respectively. We have also selected nontransparent relay stations (nt‐RSs) as relay nodes to extend the MMR network coverage. Through the nt‐RSs, far‐off subscriber stations (SSs) or hidden SSs can communicate with a base station (BS) that is connected to backhaul networks. In these MMR networks, the way in which a BS and nt‐RSs use OFDMA resources (e.g., OFDMA symbols and subcarriers) and share them might reduce system capacity and network throughput. Therefore, we proposed a new adaptive OFDMA frame structure for both the BS and the nt‐RSs. The proposed scheme is the first approach that incorporates the adaptive technique for wireless MMR networks. Based on the proposed adaptive OFDMA frame structure, an adaptive OFDMA resource allocation for SSs within a BS as well as nt‐RSs was proposed. To derive the maximum OFDMA resource that nt‐RSs can be assigned and to synchronize access zones and relay zones between a superior station and its subordinate nt‐RSs, three properties are introduced: a data relay property, a maximum balance property, and a relay zone limitation property. In addition, we propose max‐min and proportional fairness schemes of the proposed adaptive frame structure. Our numerical analysis and simulations show that the proposed OFDMA allocation scheme performs better than the nonadaptive allocation scheme in terms of network throughput and fairness especially in the asymmetric distribution of subscriber stations between access zones and relay zones in the MMR networks. Copyright © 2011 John Wiley & Sons, Ltd.

Because of the high cost of construction and maintenance of infrastructure-based networks, researchers have concentrated their efforts on studying wireless mesh/relay networks with lower cost and high scalability. Due to the demand for real-time multimedia communication in heterogeneous networks, IEEE 802.16 multi-hop mesh/relay networks with IEEE 802.11e WLANs for QoS support can be an effective multi-hop network model instead of IEEE 802.11-based mesh networks without any QoS mechanism. In addition, to provide end-to-end QoS support for different QoS mechanisms of IEEE 802.lie, IEEE 802.16, and the Internet protocol, differentiated services architecture can be applied. Therefore, we propose a design of cross-layer DiffServ architecture in wireless multi-hop mesh/relay networks with WLANs for end-to-end QoS support. Simulations of the proposed QoS architecture using OPNET Modeler show an excellent end-to-end QoS guarantee in the multi-hop mesh/relay networks.

Various vehicular communication technologies have been proposed to provide reliable and seamless wireless communications. Short-range vehicular communications can be established using IEEE 802.11p, and the range of these protocols can be extended using mobile multi-hop ad hoc networks. To provide consistent quality of service (QoS) with maximum achievable transmission rate, many algorithms assume that the signal to noise ratio (SNR) of the receiver is known, or can be obtained by modifying protocols. In this paper, we present an efficient on-demand adaptive channel estimation technique. Using simple UDP messages without changing protocols, the estimator predicts the SNR with minimum signaling overheads. Extensive experiments in vehicular environments along the I-85 highway and residential areas in Atlanta, Georgia reinforce that the proposed algorithm is efficient and reliable channel estimation technique for next generation wireless mobile networks.

Due to the high cost of construction and maintenance of infrastructure, engineers and researchers have focused their investigations on wireless mesh/relay networks with lower cost and high scalability. For current wireless mesh/relay networks, the end-to-end QoS guarantee is an important functionality because the demand for real-time multimedia communications has recently been increasing. Therefore, We propose an adaptive end-to-end delay assurance algorithm with the differentiated services architecture of hybrid mesh/relay networks with IEEE 802.16 and IEEE 802.11e to support a QoS guarantee for the mesh/relay networks. By simulating the mesh/relay networks using OPNET Modeler and analyzing the traffic of applications with different QoS requirements, we show that the proposed algorithm with the differentiated services architecture provides excellent end-to-end QoS support.

WiMAX with wired infrastructure has been popularly deployed. However, due to the high cost of the construction and the maintenance of the infrastructure, researchers have focused their investigations on IEEE 802.16 wireless multi-hop networks with low cost and high scalability. With IEEE802.11e WLANs, which provide user-level QoS support for WLANs, the multi-hop networks of IEEE 802.16 using DiffServ can provide an excellent network architecture for QoS support. In the multi-hop networks, polling services for the bandwidth request and grant play an important role for a QoS guarantee for IEEE 802.11e clients. Thus, we propose an adaptive polling algorithm with differentiation strategy for unicast and multicast polling services in IEEE 802.16 multi-hop networks with IEEE 802.11e WLANs using DiffServ to provide a QoS guarantee. By simulating the polling algorithm and the DiffServ network architecture using the OPNET Modeler and analyzing bandwidth utilization and the number of clients with rejected bandwidth requests, we show that the novel polling algorithm provides excellent QoS support.

To support the quality of service in wireless multimedia communications, wireless systems should work well in typical wireless environments characterized by the path loss of the signals, multipath fading, interference to adjacent channels, and random errors. A variety of researches in the application-layer have been proposed to adapt the video encoder to the link quality by compressing the data with different rates. However, these approaches introduce additional overhead and are inefficient when the round-trip delays are long. This paper proposes an algorithm to prevent packet losses and skipped frames by using optimal fragmentation technique with rate adaptation. Using an adaptive SNR estimator, the sender estimates the SNR of the receiver, and shapes arbitrary sized packets into optimal length packets with rate adaptation. Through rigorous analysis and extensive experiments with an implemented test-bed, we show that the algorithm significantly enhances the visual quality of real-time multimedia streaming in noisy ad hoc networks. The experimental results reinforce the fact that the algorithm is a realistic approach that can be deployed without modifying existing standards.