A note on on-line broadcast scheduling with deadlines

In this paper, we study an on-line broadcast scheduling problem with deadlines, in which the requests asking for the same page can be satisfied simultaneously by broadcasting this page, and every request is associated with a release time, deadline and a required page with a unit size. The objective is to maximize the number of requests satisfied by the schedule. In this paper, we focus on an important special case where all the requests have their spans (the difference between release time and deadline) less than 2. We give an optimal online algorithm, i.e., its competitive ratio matches the lower bound of the problem.     

Survivable millimeter-wave mesh networks

Millimeter-wave mesh networks have the potential to provide cost-effective high-bandwidth solutions to many current bandwidth-constrained networks including cellular backhaul. However, the availability of such networks is severely limited due to their susceptibility to weather, such as precipitation and humidity. In this paper, we present a rigorous approach to survivable millimeter-wave mesh networks based on experimentation, modeling, and simulation. Individual link performance is characterised using frame error-rate measurements from millimeter-wave transmissions on test links over a period of one year. A geometric model based on radar-reflectivity data is used to characterise rain storms and determine their impact on spatially correlated links of a mesh network. To mitigate the impact of link impairments on network services, we present two cross-layered routing protocols to route around the failures: P-WARP (predictive weather-assisted routing protocol) and XL-OSPF (cross-layered open shortest-path first). We conduct a performance analysis of the proposed mesh network under the presence of actual weather events as recorded by the US National Weather Service. Results show that the proposed approach yields the highest dependability when compared against existing routing methods.     

Optimal Deterministic Broadcasting in Known Topology Radio Networks

We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.A preliminary version of this paper (with a weaker result) appeared in the Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), August 2004, Harvard University, Cambridge, USA, LNCS 3122, 171–182. Research of the second author supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Part of this work was done during the second author’s visit at the Max-Planck-Institut für Informatik.     

基于IP广播的计算机远程唤醒机制及其实现

通过远程唤醒使远程主机自动加电启动,进而利用远程控制软件可对远程主机进行有效控制。基于IP广播的计算机远程唤醒机制,采用WinSock实现了计算机的远程唤醒、远程关机和重新启动,从而为远程控制计算机提供有力支持。     

山地城市小流域暴雨径流模型的研发及应用

采用ArcEngine二次开发包结合水力学基础算法,建立山地城市暴雨径流模型,以模拟山地城市降雨径流,分析山地城市排水系统的排放能力。应用该模型对重庆市北部新区盘溪河流域排水系统进行了预测和评估,结果表明,模拟结果与实测数据的效率系数Nash-Suttcliffe系数Ens为0.56～0.76,相对误差8.82%～11.8%。模型关键参数率定及敏感性分析表明,最敏感参数为径流宽度、坡度、曼宁系数和不透水面积率。针对排水管道内流量、充满度和溢流检查井个数等方面进行了排水系统排放能力的评估,结果表明,一年一遇暴雨下有0.52%的排水管道长时间处于满流状态,五十年和百年一遇的超载排水管道占排水管道总数5.86%和8.20%;百年一遇暴雨下有0.72%的检查井发生溢流,一年一遇暴雨下有0.31%的检查井发生溢流。该模型实现了对山地城市暴雨径流的产汇过程模拟以及内涝点位置和数量的识别,为城市雨水管网管理提供决策支持。     

暴雨衰减指数为函数型的暴雨强度公式确定方法

暴雨强度公式是城镇排水工程设计的基本依据之一。为提高暴雨衰减指数随重现期显著变化时暴雨强度公式的拟合精度,结合实例研究了采用麦夸尔特法确定衰减指数为函数型的五参数暴雨强度公式的方法。计算结果表明,五参数暴雨强度公式能显著提高拟合精度,由该公式计算的残差平方和及各重现期的绝对均方差(即标准差)均明显小于四参数公式的计算结果,其各重现期的绝对均方差均小于0.05mm/min。该方法能有效降低重现期较小与较大时的绝对均方差。此外,给出了麦夸尔特法的计算程序框图,为编写计算程序代码奠定基础。     

吉安市“2010·6”暴雨洪水分析

2010年6月,吉安市发生了大范围的持续暴雨洪水过程,由于本次暴雨洪水的特殊性,曾引发了一系列的洪涝灾害甚至溃堤.本文分析了该次暴雨洪水特性及重现期,有利于掌握该地区暴雨洪水的特点,为防汛减灾提供依据.     

Transient Rainfall-Runoff Loadings to a Partial Exfiltration System: Implications for Urban Water Quantity and Quality

Modification of rainfall-runoff processes by urban infrastructure and anthropogenic activities impacts receiving waters and the surrounding terrestrial environment. Infiltration–exfiltration systems such as a partial exfiltration reactor (PER) when loaded by transient sheet flow have the potential to attenuate the impact of both the quantity and quality of urban runoff. These in situ systems are subject to highly variable water quality and quantity while functioning under variably saturated flow conditions. To improve the understanding of field-scale PER performance as a rainfall-runoff unit operation and process, a two-dimensional (2D) numerical model was used to simulate the effluent hydrograph and water content profiles under transient hydraulic loadings. Richard’s equation was applied in the 2D model using parameters estimated from laboratory experiments and hydrographs measured for an in situ PER. The temporal dynamics of the water content illustrated the ability of the PER to lower peak flow, redistribute volume, and attenuate temporal aspects of the inflow hydrograph. Results demonstrated the role of the PER to attenuate runoff water quantity, while also providing water quality improvements, as illustrated for suspended solids and dissolved Cu. Simulation of historical events for different surrounding soils illustrated the critical role of surrounding soil conditions on PER performance. While the PER demonstrated water quantity attenuation benefits for design storms (1, 2, 5?year return periods), results also illustrate how a given PER design for clayey soils conditions can be limiting for intense events. Evaporation was a dominant mechanism for the drying process in the PER upper layer; with a residual moisture content in the porous pavement layer achieved in less than 2?days in summer for Cincinnati, Ohio.     

A bandwidth latency tradeoff for broadcast and reduction

The “fractional tree” algorithm for broadcasting and reduction is introduced. Its communication pattern interpolates between two well known patterns—sequential pipeline and pipelined binary tree. The speedup over the best of these simple methods can approach two for large systems and messages of intermediate size. For networks which are not very densely connected the new algorithm seems to be the best known method for the important case that each processor has only a single (possibly bidirectional) channel into the communication network.     

基于服务器转发的支持多种通信方式的通信协议

提出了一种基于服务器转发的通信协议，其能够支持广播、组播、单播这几种通信方式，支持多种类型消息的通信。介绍了该协议的功能、报文格式以及实现方法。