Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n²) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn²logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].     

Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

认知无线电网络的伺机频谱接入策略

提出了一种伺机频谱接入策略,用于由移动用户构成的认知无线电网络环境。提出的方案中,将每个可获得的信道划分成由N个时隙构成的TDMA帧,并且为每个激活的认知用户分配一个区别于其他激活用户的时隙。允许节点以一定的接入概率充分利用分配给其他激活用户的时隙进行通信。评估了提出的伺机频谱共享策略对系统吞吐量和能耗性能的影响。     

认知无线网络中动态频谱接入性能分析

认知无线电技术利用频谱空洞进行通信,有效缓解了频谱资源紧缺问题,动态频谱接入是其核心技术。网络中主用户对授权频谱的使用效率较高时,次用户接入网络无法完成符合QoS要求的通信,只有当主用户频谱效率在一定门限值下时网络才适合次用户接入。有限频谱空洞资源只能满足有限次用户的通信需求,为了保证通信质量,网络在固定的主用户频谱效率下只能接入适量的次用户。提出用强制优先排队理论对认知无线网络中的动态频谱接入过程进行模拟,通过仿真对次用户的切换概率、阻塞概率两个QoS因子进行分析,在给定的QoS条件下,得到了网络适合次用户接入的主用户频谱效率门限值,以及在固定的主用户频谱效率下网络适合接入次用户的量。     

高效的分簇传感器网络广播认证方案*

广播是无线传感器网络的重要通信手段,广播消息的安全性应得到保障。在分簇传感器网络结构基础上提出了一种无线传感器网络广播认证方案,簇头节点对广播进行签名认证,簇内使用消息认证码进行消息认证,网关节点负责广播消息在簇间的传递。分析表明,与部分现有的传感器网络广播认证方案相比,该方案以较低的能耗提供了较高的安全性。     

On the number of broadcast schemes in networks

Broadcasting is the process of spreading one piece of information among a group of individuals connected by an interconnection network. In this paper we give exact lower and upper bounds for the number of broadcast schemes in arbitrary networks. Also, we give the exact value for complete bipartite graphs and an upper bound for regular networks. Based on the counting method we describe a new random algorithm for broadcasting in networks.     

Optimal MAC based cooperative spectrum sensing in cognitive radio networks

This paper considers a cognitive radio (CR) system in non-ideal fading wireless channels and pro-poses cooperative spectrum sensing schemes based on coherent multiple access channels (MAC),serving as an alternative way to improve the cooperative spectrum sensing performance and provide space diversity for spec-trum sensing.Sufficient statistics are transmitted using a common channel from the secondary users (SUs) to a fusion center (FC) where the global decision is obtained.The optimal scaling factors of the proposed schemes are obtained by maximizing the detection probability under a target false alarm probability and a transmit power constraint.Because the proposed optimal MAC scheme has high computational complexity,a sub-optimal solu-tion based on maximization of the deflection coefficient (DC) is also proposed.Simulation results show that the proposed algorithms can significantly improve the spectrum sensing performance and approach the detection baseline.     

认知无线电网络中基于智能天线的空间频谱接入机会

认知无线电技术可以动态使用授权频段进行传输,因此如何有效利用这些频谱接入机会成为一个研究重点。本文研究在认知无线电网络中使用智能天线,使认知用户在时域上获得频谱接入能力外,还具有增强的空间复用能力。当前频段出现活跃授权用户时,认知用户可以优化天线波束模式,避免干扰授权用户同时保持在该频段上的传输。本文对波束调整的策略进行分析,并给出了使用这些策略时认知用户可以获得的空间共享概率。理论分析和仿真结果均表明,使用智能天线可以使认知用户获得更多的频谱接入机会,频段的利用率大幅提高。     

An analysis on decentralized adaptive MAC protocols for cognitive radio networks

The scarcity of bandwidth in the radio spectrum has become more vital since the demand for more and more wireless applications has increased. Most of the spectrum bands have been allocated although many studies have shown that these bands are significantly underutilized most of the time. The problem of unavailability of spectrum and inefficiency in its utilization has been smartly addressed by the cognitive radio (CR) technology which is an opportunistic network that senses the environment, observes the network changes, and then uses knowledge gained from the prior interaction with the network to make intelligent decisions by dynamically adapting their transmission characteristics. In this paper, some of the decentralized adaptive medium access control (MAC) protocols for CR networks have been critically analyzed, and a novel adaptive MAC protocol for CR networks, decentralized non-global MAC (DNG-MAC), has been proposed. The results show the DNG-MAC outperforms other CR-MAC protocols in terms of time and energy efficiency.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

认知Ad hoc网络的频谱接入跨层设计方案*

为提高分布式认知Ad hoc网络的频谱感知精准性和能量有效性,提出了一种基于能量效率的频谱接入跨层设计方案。首先通过基于感知因子的完全二分图分解法对网络进行分簇,进而在簇内联合优化次用户的发射功率和接入概率,最终得到最优信道接入和功率分配方案。仿真结果表明,与传统算法相比该方案可通过合理分簇提高分布式认知网络的感知精度,在保证感知性能的条件下使系统能量效率得到有效提升。     

基于随机线性网络编码的改善无线网络广播能量效率的方法*

提出了一种应用网络编码技术改善无线网络广播能量效率的分布式完全编码广播策略（DAEBNC）,其核心思想是发送节点通过获得邻居节点记录数据的情况,应用随机线性网络编码选择多个源数据包生成编码组合包,依次发送;接收节点使用线性运算解码编码包获得源数据包。理论分析表明,该方法编码包在所有接收节点具有可解性,有效地减少了数据广播次数。仿真结果证实,与普通泛洪方法相比,DAEBNC可以有效地提高能量利用效率,改善无线网络性能。     

基于能量效率的认知无线网络联合优化算法

为提高认知无线网络能量有效性,提出一种基于能量效率的联合优化算法。在考虑主用户干扰容限的基础上构建了能量有效性模型,将优化目标分解为接入策略求解和功率优化问题,采用粒子群算法反复迭代,得到接入概率与功率分配的联合最优解。仿真结果表明,相对于不考虑功率优化或接入概率的传统优化方法,所提算法可使系统能量效率得到显著提升。     

Vulnerabilities in cognitive radio networks: A survey

Cognitive radio networks are envisioned to drive the next generation wireless networks that can dynamically optimize spectrum use. However, the deployment of such networks is hindered by the vulnerabilities that these networks are exposed to. Securing communications while exploiting the flexibilities offered by cognitive radios still remains a daunting challenge. In this survey, we put forward the security concerns and the vulnerabilities that threaten to plague the deployment of cognitive radio networks. We classify various types of vulnerabilities and provide an overview of the research challenges. We also discuss the various techniques that have been devised and analyze the research developments accomplished in this area. Finally, we discuss the open research challenges that must be addressed if cognitive radio networks were to become a commercially viable technology.     

T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.