Efficient routing and centralized scheduling algorithms for IEEE 802.16 Mesh Networks

An IEEE 802.16 wireless system can provide broadband wireless access to subscriber stations and operate in mesh mode. The communication between a subscriber station and a base station can pass through one or more intermediate subscriber stations. The IEEE 802.16 standard provides a centralized scheduling mechanism that supports contention‐free and resource‐guarantee transmission services in mesh mode. However, the corresponding algorithm to this schedule is quite primitive in the standard. In this paper, we propose a more efficient way to realize this schedule by maximizing channel utilization. Our designs are divided into two phases: routing and scheduling. First, a routing tree topology is constructed from a given mesh topology by our proposed tree construction algorithm. Secondly, we allocate channel resources to the edges in the routing tree by our proposed scheduling algorithm. To further support the quality‐of‐service schedule, we extend our designs by addressing some issues such as service class, admission control and fairness. Simulation results show the superiority of our proposed algorithms over others. Copyright © 2011 John Wiley & Sons, Ltd.     

Combined Random/Reservation Access for Packet Switched Transmission Over a Satellite with On-Board Processing: Part I--Global Beam Satellite

A combined random/reservation multiple access (CRRMA) scheme for packet-switched communication over a global beam satellite with on-board processing is proposed and analyzed. Channel time is divided into contiguous slots; each slot containsNminislots for transmission of request packets andN'minislots for data. WithNsubstantially smaller than the number of earth stations, collisions will occur in request packet transmissions. Two channel access algorithms for the CRRMA model are proposed: uncontrolled channel access (UCA) and controlled channel access (CCA). UCA is simpler but has an inherent stability problem particularly when the number of minislotsNis small. The CCA algorithm restricts the transmission of request packets for new arrivals to take place only when the slot is in the FREE state. WithN = 3, the CCA algorithm exhibits good delay-throughput characteristics. AsNincreases, the UCA algorithm offers stable operation. ForN geq 5the simpler UCA algorithm is preferred over CCA.     

Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks

Time division multiple access (TDMA) based medium access control (MAC) protocols can provide QoS with guaranteed access to the wireless channel. However, in multi-hop wireless networks, these protocols may introduce scheduling delay if, on the same path, an outbound link on a router is scheduled to transmit before an inbound link on that router. The total scheduling delay can be quite large since it accumulates at every hop on a path. This paper presents a method that finds conflict-free TDMA schedules with minimum scheduling delay. We show that the scheduling delay can be interpreted as a cost, in terms of transmission order of the links, collected over a cycle in the conflict graph. We use this observation to formulate an optimization, which finds a transmission order with the min-max delay across a set of multiple paths. The min-max delay optimization is NP-complete since the transmission order of links is a vector of binary integer variables. We devise an algorithm that finds the transmission order with the minimum delay on overlay tree topologies and use it with a modified Bellman-Ford algorithm, to find minimum delay schedules in polynomial time. The simulation results in 802.16 mesh networks confirm that the proposed algorithm can find effective min-max delay schedules.     

Analysis of contention tree algorithms

The Capetanakis-Tsybakov-Mikhailov (1978, 1979) contention tree algorithm provides an efficient scheme for multiaccessing a broadcast-communication channel. This paper studies the statistical properties of multiple-access contention tree algorithms with ternary feedback for an arbitrary degree of node. The particular quantities under investigation are the number of levels required for a random contender to have successful access, as well as the number of levels and the number of contention frames required to provide access for all contenders. Through classical Fourier analysis approximations to both the average and the variance are calculated as a function of the number of contenders n. It is demonstrated that in the limit of large n these quantities do not converge to a fixed mode, but contain an oscillating term as well     

Dynamic reservation TDMA protocol for wireless ATM networks

A dynamic reservation time division multiple access (DR-TDMA) control protocol that extends the capabilities of asynchronous transfer mode (ATM) networks over the wireless channel is proposed in this paper. DR-TDMA combines the advantages of distributed access and centralized control for transporting constant bit rate (CBR), variable bit rate (VBR), and available bit rate (ABR) traffic efficiently over a wireless channel. The contention slots access for reservation requests is governed by the framed pseudo-Bayesian priority (FPBP) Aloha protocol that provides different access priorities to the control packets in order to improve the quality-of-service (QoS) offered to time sensitive connections. DR-TDMA also features a novel integrated resource allocation algorithm that efficiently schedules terminals' reserved access to the wireless ATM channel by considering their requested bandwidth and QoS. Integration of CBR, voice, VBR, data, and control traffic over the wireless ATM channel using the proposed DR-TDMA protocol is considered in this paper. Simulation results are presented to show that the protocol respects the required QoS of each traffic category while providing a highly efficient utilization of approximately 96% for the wireless ATM channel     

Allocation and scheduling algorithms for IEEE 802.14 and MCNS inhybrid fiber coaxial networks

IEEE 802.14 and MCNS (multimedia cable network system) are two standards developed for the hybrid fiber coaxial (HFC) CATV networks. Both standards model an upstream channel as a stream of minislots. But their philosophies on resolving collisions in the shared upstream channel are rather different, where IEEE 802.14 adopts the priority+FIFO first-transmission rule and the n-ary tree retransmission rule, and MCNS adopts the binary exponential backoff algorithm with adjustable window sizes. Both provide reservation access, while IEEE 802.14 and MCNS also support isochronous access and immediate access, respectively. In this paper, we try to prepare a suggestion list for vendors on how to allocate minislots for reservation access and immediate access and how to schedule the reserved bandwidth, which greatly affect the performance of a cable network and are left open by the standards     

Analysis of an identifier splitting algorithm combined with polling(ISAP) for contention resolution in a wireless access network

A contention resolution scheme for an uplink contention channel in a wireless access network is presented. The scheme consists of a tree algorithm, namely the identifier splitting algorithm (ISA), combined with a polling scheme. Initially, ISA is used, but at a certain level of the tree, the scheme switches to polling of the stations. This scheme is further enhanced by skipping a few levels in the tree when starting the algorithm (both in a static and a dynamic way) and by allowing multiple instants simultaneously. An analytical model of the system and its variants leads to the evaluation of its performance, by means of the delay density function and the throughput characteristics. This model is used to investigate the influence of the packet arrival rate, the instant at which the ISA scheme switches to polling, the starting level of the ISA scheme, and the use of multiple instances on the mean delay, the delay quantiles, and the throughput     

An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels

A basic problem in the decentralized control of a multiple access channel is to resolve the conflicts that arise when several stations transmit simultaneously to the channel. Capetanakis, Hayes, and Tsybakov and Mikhailov found a deterministic {em tree algorithm} that resolves conflicts amongkstations from an ensemble ofnin timeTheta (k + k log (n / k))in the worst case. In this algorithm, at each step, the choice of which stations to enable to transmit depends crucially on feedback information provided by the channel. We show that ifkis given {em a priori} then such conflicts can be resolved in timeTheta (k + k log (n / k))using an algorithm in which the corresponding choices do not depend on feedback.     

Virtual Time CSMA: Why Two Clocks Are Better than One

A new carrier sense multiple access (CSMA) algorithm, called virtual time CSMA, is described and analyzed. This algorithm uses a novel approach to granting access to the shared broadcast channel based on variable-rate clocks. Unlike other CSMA algorithms, the operation of virtual time CSMA reduces to the ideal case in the zero propagation time limit: a work-conserving, first-come first-servedM/G/1queueing system. The algorithm does not appear to be difficult to implement, but offers better throughput-delay performance than existing CSMA algorithms. A simple closed form technique for estimating the mean message delay is presented. This technique is of independent interest because of its applicability to certain "sliding window" tree conflict resolution algorithms. Extensive numerical results for the algorithm are presented, including comparisons with simulation and with other CSMA algorithms.     

第三方探测系统目标身份获取算法设计与实现

针对第三方手持探测系统对目标身份识别的技术需求,设计开发了第三方探测系统目标身份获取算法。以TD-SC-DMA系统为设计实例,算法包括下行链路广播消息解析,主公共控制物理信道与物理随机接入信道的配置信息提取,上行链路主公共控制物理信道与物理随机接入信道监控及消息处理,实现用户身份标识的获取。将该算法移植至硬件平台进行编译实现,通过测试验证该探测算法的有效性。     

Free access stack algorithms for microcellular radio systems

We evaluate the data traffic performance of a centralized packet access protocol for microcellular radio systems supporting both speech and data users. A time-slotted radio channel is assumed. Speech contention is decoupled from data contention to give speech priority over data. A free access stack algorithm is used for handling data contention. An out-slot access scheme is used in which the slots are divided into user-information transmission slots and contention slots for sending transmission requests. The contention slots are subdivided in minislots to improve the access capacity. The out-slot algorithm performances are compared with the performances of a previously proposed in-slot one in which all slots can be used for sending user information. A memoryless channel, with capture and errors, is considered. The effects of speech traffic on data performance are evaluated. Moreover, the paper presents a method for evaluating the packet error probability of a packet cellular system. This method is used for evaluating the proposed algorithm in a microcellular system. An access technique with coordinated operation among cochannel cells is studied. The effects of sectorization on data performances and protocol unfairness are investigated. Different frequency reuse factors are taken into consideration     

Announced Retransmission Random Access Protocols

A new contention-based broadcast multiaccess protocol called announced retransmission random access (ARRA) is introduced and analyzed in this paper. The proposed class of protocols increases the capacity of a slotted random access channel by adding a small amount of potentially useful control information to every message transmission. In particular, the ARRA technique requires users to announce the intended location of their potential retransmission slot (to be used in the event of a collision) over a low-rate announcement subchannel, so that conflicts between new and retransmitted messages can be prevented. The proposed protocols provide significant capacity improvements over conventional contention protocols, without sacrificing the simplicity and operational convenience associated with random access. It is shown that with a modest amount of processing and storage at the terminals, capacities in the range of 0.5-0.6 can be achieved, as compared with 0.37 for slotted ALOHA and 0.4-0.5 for the more efficient tree algorithm-based collision resolution algorithms (CRA's). Specifically, the basic ARRA protocol, in which announced retransmissions take place unconditionally, has a capacity of about 0.53. An improved algorithm (called extended ARRA), which involves aborting predictably unsuccessful retransmissions, has a capacity of 0.6. In addition, because of delay considerations, the proposed ARRA protocols are well suited for operation on satellite channels.     

Low Access Delay Anti-Collision Algorithm for Readers in Passive RFID Systems

Even though radio frequency identification (RFID) systems are spreading more and more as a medium for identification, location and tracking purposes, some reliability issues of these systems still need to be solved. In fact, RFID readers and tags experience collisions when sharing the wireless transmission channel over the same area. In this work, we propose a centralized scheduling-based algorithm as possible candidate solution for the reader collision problem in passive RFID systems. This algorithm has been designed taking into account the circuitry limitations of the tags, which do not allow the usage of frequency or code division multiple access schemes in passive RFID systems. The solution herewith proposed, which is suitable for those scenarios involving static or low mobility readers, aims at preventing reader collisions and provides at the same time low channel access delay to the readers. The performance of this algorithm has been tested via computer simulations. The results show that the proposed solution strongly reduces collision occurrences and, especially in static scenarios, provides low access delay to the readers during the channel contention phase.     

一种新的基于自适应步长的二级CMA盲接收机

在高速数据传输的频率选择性信道的直接序列扩频系统中,基于恒模算法（CMA）的二级盲接收机能够在只知道期望用户的扩频码以及定时信息的情况下进行自适应联合均衡和多用户检测,具有较好的实时处理性能。但是其第一级检测器的自适应求取采用的是递归最小二乘（RLS）算法,该算法在收敛稳定性等方面具有一系列缺陷,从而对整个算法的性能造成了损害。本文将戴彧虹 袁亚湘自适应步长迭代算法作为第一级检测器的自适应处理方式,并给出了新的方案的完整实现流程。理论和仿真结果显示,经过改进后的二级CMA盲自适应接收机比起原先的算法有着更低的误码率和更高的稳态输出信干比（SINR）,在总体性能上有了很大提高。      

A limited sensing random-access algorithm with binarysuccess-failure feedback

The authors consider the problem of random access communication over a time-slotted channel, with binary success/failure feedback. The feedback informs the users only whether or not there was a success (single transmission) in the previous slot. They propose and analyze a limited feedback-sensing algorithm (each user is required to observe the channel feedback, from the time he generates a packet to the time that this packet is successfully transmitted). The algorithm requires central control implemented by a central receiver. The limit Poisson user model is adopted. The algorithm achieves a throughput of 0.322 and induces low delays for relatively low input rates     

Computational moments for sequential decoding of convolutional codes

The long standing conjecture is established that, for a discrete memoryless channel, there exists a linear convolutional code with infinite constraint length such that therhoth(rho geq 1)moment of the number ofF-hypotheses in the Fano sequential decoding algorithm is bounded, provided that the transmission rateRis less thanE_{0}( rho,r)/ rho, wherer(x)is a distribution over the channel input alphabet. A new concept of independence for a finite set of message sequences plays an essential role in averaging a product of likelihood ratios over an ensemble of code sequences in a code tree. A simpler version of the method can be applied to the proof of the conjecture for general tree codes.     

Tree algorithms for packet broadcast channels

The multiaccessing of a broadcast communication channel by independent sources is considered. Previous accessing techniques suffer from long message delays, low throughput, and/or congestion instabilities. A new class of high-speed, high-throughput, stable, multiaccessing algorithms is presented. Contentions resolving tree algorithms are introduced, and they are analyzed for specific probabilistic source models. It is shown that these algorithms are stable (in that all moments of delay exist) and are optimal in a certain sense. Furthermore, they have a maximum throughput of 0.430 packets/slut and have good delay properties. It is also shown that, under heavy traffic, the optimally controlled tree algorithm adaptively changes to the conventional time-division multiple access protocol.     

一种基于FEC-MDC的多用户码流快速分割算法

基于前向纠错的多描述编码（FEC-MDC）是一种在包丢失严重的信道中传输可分级图像和视频数据的有效方法。本文针对单一信源多用户的网络应用模型,研究了在描述数N固定的情况下,根据各信道传输码率的不同,通过调整发送包的长度L实现最佳码流传输的问题,提出了一种码流快速优化分割的改进算法。该算法基于已计算出的参考信道码流分割方案,在期望失真最小的准则下,首先通过在各个目标码率的邻域进行搜索计算,将搜索域分割为低码率部分和高码率部分,然后在高码率部分进行粗的二次搜索,得到最终码流分割,这不仅减少了搜索次数,降低了计算的复杂度,而且保证搜索到在该码率情况下的最佳分割。实验结果表明,本文提出的改进算法与之前的方法相比能够得到相同的平均PSNR,但是总的运算时间减少了近40%。      

卫星通信系统两步随机接入技术研究

为了实现卫星通信系统低延迟高可靠接入,研究了两步随机接入技术中的信道设计及接收端检测算法.针对卫星场景提出了一种两步随机接入信道设计方案,对两步随机接入信道中数据部分的信道结构以及前导和数据之间的映射方式进行了设计.针对传统最小均方串行干扰消除(Minimum Mean Squared Error-Successive Interference Cancellation,MMSE-SIC)算法中存在误差传播问题导致解码性能降低的问题,提出了一种多判决排序串行干扰消除(Multi-decision Ordered Successive Interference Cancellation,MD-OSIC)算法,以提升多用户发起接入时数据部分检测的可靠性.仿真结果验证了所设计信道及检测算法在典型卫星通信场景下应用的可行性.     

分组N叉跟踪树型RFID防碰撞算法研究

针对无线射频识别(RFID,Radio Frequency Identification)标签多路访问产生的信号碰撞问题,提出了基于碰撞位跟踪的分组N叉跟踪树型RFID防碰撞算法(CBGN,Collision Bit Tracking Tree Algorthm Based on Grouping N-ray).利用极大似然位估算法(MLE,Maximum Likelihood Bit Estimation)估算应用环境下标签的数量.在MLE基础上根据标签标识(ID)将标签分配在不同分组内,并利用N叉树识别分组后的标签,CBGN算法通过分组及N叉识别两种策略相结合来降低碰撞概率及识别延时.最后,以通信复杂度为基准对不同N叉树下的最优分组系数进行了推导,从而获得最优N值及对应分组系数.理论分析和仿真实验表明,CBGN算法具有鲁棒性好和通信复杂度低的特点.