Zhen Yang, Ping Jian, Zhongbin Guo, Zuming Zhang, Chengzhi Li, Yonghong Deng, Xinyue Zhang, Wenpeng Lu. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Zhen Yang, Ping Jian, Chengzhi Li. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

We study the connectivity of overlaid wireless networks where two users can communicate if the signal-to-interference ratio is larger than a threshold subject to an outage constraint. By using percolation theory, we first specify a 2-dimensional connectivity region defined as the set of density pairs-the density of secondary users and the density of primary users- within which the secondary network is percolated. Several interesting properties of this region are also revealed. Our work provides a new perspective for better understanding of the connectivity of large-scale overlaid networks.

Connectivity is crucial to ensure information availability and survivability for wireless networks. In this paper, we propose a unified framework to study the connectivity of wireless networks under a general type of interference attack, which can address diverse applications including Cognitive Radio, Jamming attack and shadowing effect. By considering the primary users, jammers and deep fading as unified Interferers, we investigate a 3-dimensional connectivity region, defined as the set of key system parameters - the density of users, the density of Interferers and the interference range of Interferers - with which the network is connected. Further we study the impact of the Interferers' settings on node isolation probability, which is a fundamental local connectivity metric. Through percolation theory, the sufficient and necessary conditions for global connectivity are also derived. Our study is supported by simulation results.

In order to improve the spectrum efficiency, spectrum sharing systems allow multiple systems to utilize the same spectrum with different priorities. Typically, the primary network performs as a stand-alone network while the secondary one accesses the spectrum only if it does no harm to the primary receivers. In this paper, the configuration of the secondary network is of our interest and we explore its single-hop transport throughput (STT) with outage constraints imposed on both networks. STT is a new metric that inherits the merits of both the traditional transport capacity and transmission capacity, incorporating transmission distance and outage probability into a uniform framework. Given the settings of the primary network, we first evaluate the limit of the secondary STT, single-hop transport capacity (STC). Then, we investigate STT with secondary receivers randomly located in the field of interest. To provide a comprehensive view of achievable secondary network throughputs, three models regarding the selection of receivers are considered: optimally selected, randomly selected, and the nearest neighbors. Our theoretical analysis are well substantiated by numerical and simulation results.

Jamming attacks can cause serious destruction to communication systems without much cost, especially when secret keys shared by the system are exposed. Uncoordinated Frequency Hopping (UFH) is an effective countermeasure to jamming attacks without dependence on pre-shared secret keys. In this paper we study the connectivity of a multi-channel network under jamming attacks, where each communication link can switch from regular transmission to UFH transmission when jamming attacks are detected. Under the framework of percolation theory, we show that as the jammer density increases, two phase transitions occur: from strong connection where there exists an infinite component composed of regular links, to weak connection where there exists an infinite component composed of both regular and UFH links, then to disconnection.

In this paper, we study distributed function computation in a noisy multihop wireless network. We adopt the adversarial noise model, for which independent binary symmetric channels are assumed for any point-to-point transmissions, with (not necessarily identical) crossover probabilities bounded above by some constant $(\epsilon)$. Each node takes an $(m)$-bit integer per instance, and the computation is activated after each node collects $(N)$ readings. The goal is to compute a global function with a certain fault tolerance in this distributed setting; we mainly deal with divisible functions, which essentially cover the main body of interest for wireless applications. We focus on protocol designs that are efficient in terms of communication complexity. We first devise a general protocol for evaluating any divisible functions, addressing both one-shot $((N = O(1)))$ and block computation, and both constant and large $(m)$ scenarios. We also analyze the bottleneck of this general protocol in different scenarios, which provides insights into designing more efficient protocols for specific functions. In particular, we endeavor to improve the design for two exemplary cases: the identity function, and size-restricted type-threshold functions, both focusing on the constant $(m)$ and $(N)$ scenario. We explicitly consider clustering, rather than hypothetical tessellation, in our protocol design.

Overlaid networks, typically composed of primary and secondary networks, are emerging as a viable candidate to resolve the conflict between increasing demand for spectrum and spectrum shortage. The essential purpose of overlaid networks is to improve the network spectrum efficiency, which, however, may not be achieved if the secondary network is inappropriately configured. In decentralized overlaid networks, the throughput of the primary network will decrease due to the extra interference from the secondary network, and its loss may not be compensated by the throughput gained by the secondary network. This motivates us to study the overall throughput of the overlaid networks. In particular, we examine the overall transmission throughput, which is a variation of the transmission capacity, a popular metric in the study of decentralized networks. Our study provides a sufficient condition for the secondary network setting such that the overall throughput is improved over that of a stand-alone primary network. In addition both the maximal allowable secondary density and the optimal secondary density which maximizes the overall throughput are derived.

Due to the emergence of Cognitive Radio, a special type of heterogeneous networks attracts increasing interest recently, in which a secondary network composed of cognitive users shares the same resources opportunistically with a primary network of licensed users. Network throughput in this setting is of essential importance. Some pioneer works in this area showed that this type of heterogeneous networks performs as well as two stand-alone networks, under the dense network model where the size of a network grows with the node density in a fixed area. A key assumption behind this conclusion is that the density of the secondary network is higher than that of the primary one in the order sense, which essentially decouples the two overlaid networks, as the secondary network dominates asymptotically. In this paper we endeavor to investigate this problem with a weaker condition that the dimensions of the two overlaid networks are on the same order, and consider the extended network model where the size of a network scales with the area with the node density fixed. Surprisingly, our analysis shows that this weaker (and arguably more practical) condition does not degrade either network throughput in terms of scaling law. Our result further reveals the potentials of CR technology in real applications.

Spectrum sharing systems such as cognitive radio networks have drawn much attention recently due to their potential to resolve the conflict between increasing demand for spectrum and spectrum shortage. Such systems are typically composed of primary and secondary networks; the configuration of the latter depends on spectrum opportunity unexploited in the former. In this paper we explore the characteristics of the single hop transport throughput (STT) of the secondary network with outage constraints imposed on both networks. STT is a new metric that inherits the merits of both the traditional transport capacity and another popular metric, transmission capacity, incorporating transmission distance and outage probability into a uniform framework. We first derive the limit of STT, single hop transport capacity (STC), together with a practical upper bound for it. Then we investigate STT with secondary receivers randomly located in the field of interest. Three models regarding the selection of receivers are considered: optimally selected, randomly selected, or the nearest. Study on these models provides a comprehensive view of achievable secondary network throughput, and offers insights into the configuration of secondary networks. In addition, the broadcast transport throughput (BTT) of the secondary networks is also investigated as an extension of STT, and its similarity with STT in the nearest neighbor model is revealed.

In this paper we study distributed function computation in a noisy multi-hop wireless network, in which n nodes are uniformly and independently distributed in a unit square. We adopt the adversarial noise model, for which independent binary symmetric channels are assumed for any point-to-point transmissions, with (not necessarily identical) crossover probabilities bounded above by some constant ¿. Each node holds an m-bit integer per instance and the computation is started after each node collects N readings. The goal is to compute a global function with a certain fault tolerance, in this distributed setting; we mainly deal with divisible functions, which essentially covers the main body of interest for wireless applications. We focus on protocol designs that are efficient in terms of communication complexity. We first devise a general protocol for evaluating any divisible functions, addressing both one-shot (N = O(1)) and block computation, and both constant and large m scenarios; its bottleneck in different scenarios is also analyzed. Based on this analysis, we then endeavor to improve the design for two special cases: identity function, and some restricted type-threshold functions, both focusing on the constant m and N scenario.

In this paper we study two basic properties, capacity and connectivity, of Cognitive Radio networks. Our goal is to quantitatively characterize the relationship and tradeoff among key system parameters involved in these properties, incorporating channel randomness and interference into the performance analysis. In particular, we explore the characterization of a capacity metric, single-hop transport capacity, with respect to arbitrarily and randomly located receivers, and investigate a fundamental connectivity metric, node isolation probability. The tradeoff between capacity and connectivity is also revealed.

Quickest detection is applied in spectrum sensing in cognitive radio systems when multiple secondary users collaborate with limited communication time slots. When the transmissions of sensing results are not coordinated to avoid confliction, random broadcast is used to exchange information. A necessary condition for the optimal broadcast probability, as a function of the log likelihood ratio of local observation, is obtained using variational analysis. To alleviate the difficulty of computing the optimal broadcast probability, a simple threshold broadcast scheme is proposed. Simulation shows that the proposed threshold broadcast scheme can achieve substantial performance gain (less than 60% in detection delay for the same false alarm rate) over schemes of random broadcast without regulation and single-user spectrum sensing.

Quickest detection is applied in the spectrum sensing of cognitive radio systems when multiple secondary users collaborate with limited communication time slots. When transmissions are not coordinated to avoid collisions, random broadcast is used to exchange information. A necessary condition for optimal broadcast probability, as a function of the log likelihood ratio of local observation, is obtained using variational analysis. To alleviate the difficulty of computing optimal broadcast probability, a simple threshold broadcast scheme is proposed. Simulation shows that the proposed threshold broadcast scheme can achieve substantial performance gain (less than 60% in detection delay for the same false alarm rate) over random broadcast without regulation, as well as the single-user spectrum sensing.

Quickest detection of an abrupt distribution change with an unknown time varying parameter is considered. A novel adaptive approach is proposed to tackle this problem, which is shown to outperform the celebrated Parallel CUSUM Test. Performance is evaluated through theoretical analysis and numerical simulations.

Considerations of realistic channel dynamics motivate the design of a new breed of opportunistic schemes, such as opportunistic transmission, scheduling and routing. Compared to their deterministic counter part, opportunistic schemes have been shown to increase network throughput, and/or reduce delay in limited experimental/simulation scenarios. In this paper, we propose analytical models that characterize the performance of routing protocols in lossy wireless networks with Rayleigh fading channels. We investigate the efficiency of a few representative deterministic and opportunistic routing protocols under both light-loaded and saturated traffic conditions. This work deviates from existing work that assumes idealistic packet reception, and is thus of practical relevance. Our study shows that opportunistic routing significantly outperforms its deterministic counterpart in average effective progresses made in single-hop transmissions. In deterministic routing schemes, tuning of parameters based on node density is critical to achieve optimal performance.

A key issue in supporting quality of service (QoS) over wireless networks is to estimate the wireless channel capacity that varies randomly with time and space. In this paper, we propose a new model named effective channel capacity to predict the available channel capacity during any given time interval with the required degree of confidence. By leveraging large deviations techniques, we relate the fading channel capacity with the theory of effective bandwidth and establish a connection between the theory of effective bandwidth and information theory. We derive a set of algorithms and apply them to Nakagami-m fading channels. Consequently, our results provide a foundation for the performance analysis of upper layer algorithms and protocols for QoS provisioning over wireless networks

In this paper, we propose a new model named effective fade duration envelope to characterize the accumulative conditional fade durations of individual users or groups of users in wireless communication systems. The proposed model has the following novelties: (1) it introduces the statistical upper and lower bounds with the required degree of confidence for accumulative conditional fade durations during any given time interval; (2) it characterizes various conditional fading circumstances in wireless multi-user communication systems.

When setting up a sensor network, one of the first requirements is to establish cryptographic keys to provide encrypted communication links. However, the traditional key establishment techniques cannot be directly applied due to the inherent properties of sensor networks. Recently, several random key pre-distribution schemes based on symmetric cryptography have been proposed to solve the key establishment issue of sensor networks. In this paper, we propose a framework, Blom-based Q-composite (BBQ) scheme, which generalizes various random key pre-distribution schemes. With the aid of BBQ, we systematically analyze, characterize, and discuss the properties of various random key pre-distribution schemes, including connectivity, scalability and security

In this paper, we propose a theoretical framework to analyze the performance of upper layer algorithms and protocols such as scheduling disciplines which exploit the gain of multi-user diversity to optimize the utilization of wireless communication systems while supporting service differentiation between different users.

Inter-server coordinated scheduling is a mechanism for downstream nodes to increase or decrease a packet's priority according to the congestion incurred at upstream nodes. In this paper, we derive an end-to-end schedulability condition for a broad class of coordinated schedulers that includes Core-stateless Jitter Virtual Clock (CJVC) and Coordinated Earliest Deadline First (CEDF). In contrast to previous approaches, our technique purposely allows flows to violate their local priority indexes while still providing an end-to-end delay bound. We show that under a simple priority assignment scheme, coordinated schedulers can outperform WFQ schedulers, while replacing per-flow scheduling operations with a simple coordination rule. Finally, we illustrate the performance advantages of coordination through numerical examples and simulation experiments.

This work presents a new MAC protocol called RMAC that supports reliable multicast for wireless ad hoc networks. By utilizing the busy tone mechanism to realize multicast reliability, RMAC has the following three novelties: (1) it uses a variable-length control frame to stipulate an order for the receivers to respond, such that the problem of feedback collision is solved; (2) it extends the traditional usage of busy tone for preventing data frame collisions into the multicast scenario; and (3) it introduces a new usage of busy tone for acknowledging data frames. In addition, we also generalize RMAC into a comprehensive MAC protocol that provides both reliable and unreliable services for all the three modes of communications: unicast, multicast, and broadcast. Our evaluation shows that RMAC achieves high reliability with very limited overhead. We also compare RMAC with other reliable multicast MAC protocols, showing that RMAC not only provides higher reliability but also involves lower cost.

In multihop networks, packet schedulers at downstream nodes have an opportunity to make up for excessive latencies due to congestion at upstream nodes. Similarly, when packets incur low delays at upstream nodes, downstream nodes can reduce priority and schedule other packets first. The goal of this paper is to define a framework for design and analysis of coordinated multihop scheduling (CMS) which exploits such internode coordination. We first provide a general CMS definition which enables us to classify a number of schedulers from the literature, including G-EDF, FIFO+, CEDF, and work-conserving CJVC as examples of CMS schedulers. We then develop a distributed theory of traffic envelopes which enables us to derive end-to-end statistical admission control conditions for CMS schedulers. We show that CMS schedulers are able to limit traffic distortion to within a narrow range resulting in improved end-to-end performance and more efficient resource utilization. Consequently, our technique exploits statistical resource sharing among flows, classes, and nodes, and our results provide the first statistical multinode multiclass admission control algorithm for networks of work conserving servers.

Providing quality of service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority back-off schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termedmulti-hop coordinationso that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.

We propose an approach to flow-unaware admission control which is a combination with an aggregate packet forwarding scheme, improving scalability of networks while guaranteeing end-to-end deadlines for real-time applications. We achieve this by using an off-line delay computation and verification step, which allows to reduce the overhead at admission control while keeping admission probability and resource utilization high. Our evaluation data show that our system's admission probabilities are very close to those of significantly more expensive flow-aware approaches. At the same time, the admission control overhead during flow establishment is very low. Our results therefore support the claim from the DS architecture literature that scalability can be achieved through flow aggregation without sacrificing resource utilization and with significant reduction in run time overhead.

In multi-hop networks, packet schedulers at downstream nodes have an opportunity to make up for excessive latencies due to congestion at upstream nodes. Similarly when packets incur low delays at upstream nodes, downs stream nodes can reduce priority and schedule other packets first. The goal of this paper is to define a framework for design and analysis of coordinated network scheduling (CNS) which exploit such inter-node coordination. The first provide a general CNS definition which enables us to classify a number of schedulers from the literature including, FIFO+, CEDF and work-conserving CJVC as examples of CNS schedulers. We then develop a distributed theory of traffic envelopes which enables us to derive end-to-end statistical admission control conditions for CNS schedulers. We show that CNS schedulers are able to limit traffic distortion to within a narrow range resulting in improved end-to-end performance and more efficient resource utilization.

In this paper, we present a methodology to use utilization-based admission control in guaranteed real-time communication in a scalable fashion. We make admission control scalable by using a configuration-time test to determine a safe utilization level of servers. Admission control at run-time then is reduced to simple utilization tests on the servers along the path of the new flow. Furthermore, we discuss how appropriate route selection improve utilization levels, design a safe route selection heuristic algorithm to achieve high utilization of resources, and derive two bounds on the maximum utilization level for given traffic in a network. We compare the results of our route selection heuristics with that of a shortest-path based algorithm, and find that our heuristics can achieve a much higher maximum utilization level than that of the shortest-path based algorithm.

The implementation of bounded-delay services over integrated services networks relies admission control mechanisms that in turn use end-to-end delay computation algorithms. For guaranteed-rate scheduling algorithms such as fair queueing, delay computation based on Cruz's service curve model performs very well. Many currently deployed networks, be they packet-switched or ATM based, rely on non-guaranteed-rate disciplines, most prominently FIFO and static-priority disciplines. We show that for this class of disciplines the service curve model performs poorly. We propose the Integrated Approach as alternative to the service curve model to cluster servers for delay computation purposes, and show in a series of evaluations that this new approach outperforms approaches based on the service curve model as well as other currently used approaches.

This paper presents a new schedulability analysis methodology for distributed hard real-time systems with bursty job arrivals. The schedulability is analyzed by comparing worst-case response times of jobs with their timing constraints. We compute response times with a new method, which uses the amount of received service time to determine the response time of instances of a job. We illustrate how this method can be applied to exactly determine worst-case response times for processors with preemptive static priority schedulers, and how it gives a good approximation on the response times for processors with non-preemptive static-priority scheduling or first-come-first-served scheduling. Our schedulability analysis method is the first to support systems with arbitrary job arrival patterns. Nevertheless, it performs better than other known approaches used for systems with periodic job arrivals.

We address the issues of stability in ATM networks. A network is stable if and only if all the packets have a bounded delay. We first consider ATM networks with an FCFS scheduling policy. We then study networks with a priority driven scheduling policy. For each network, we develop criteria for testing the stability of an ATM network and methods of deriving delay bounds in a stable network. In previous work, the Cruz-Gallager-Parekh (1991, 1992) ring has been a "benchmark" architecture to study the stability problem. For example, Gallager and Parerkh (1993) claimed that the ring with a size of no more than four switches is stable when the total utilization of the links is less than 100%. We validated this result. Furthermore, we find that a ring with large number of switches is stable if the utilization of each link is less than or equal to 73%.

Static priority scheduling is popular for traffic scheduling in ATM switches because it is less costly than dynamic priority scheduling while being sensitive to the delay constraints of connections. We study delay computation and priority assignment problems in an ATM network with static priority scheduling. Given an ATM network with arbitrary topology, it is possible that the traffic on it may become unstable (i.e., packet delays become unbounded) due to the potential cyclic dependency of the traffic. An unstable network is definitely unacceptable for many delay sensitive applications. We start by formally deriving a simple condition under which the network is guaranteed to be stable. We then develop a numerical method to compute worst case end to end delays in an ATM network with arbitrary topology. Convergence of the method is formally proved and a closed form for the computing error is obtained. Despite its advantages, static priority scheduling remains sensitive to proper priority assignment. We describe two simple priority assignment methods, which we show to outperform other commonly used methods.