Rare event simulation for highly dependable systems with fast repairs

Probabilistic model checking has been used recently to assess, among others, dependability measures for a variety of systems. However, the numerical methods employed, such as those supported by model checking tools such as PRISM and MRMC, suffer from the state-space explosion problem. The main alternative is statistical model checking, which uses standard Monte Carlo simulation, but this performs poorly when small probabilities need to be estimated. Therefore, we propose a method based on importance sampling to speed up the simulation process in cases where the failure probabilities are small due to the high speed of the system’s repair units. This setting arises naturally in Markovian models of highly dependable systems. We show that our method compares favourably to standard simulation, to existing importance sampling techniques, and to the numerical techniques of PRISM.     

LTL概率模型检验工具的实现与优化

概率模型检验建立在非概率模型检验技术的基础上,不仅能够对系统进行定性的验证,还能够定量判断系统满足相关性质的概率,具有广泛的适用性。LTL概率模型检验算法的复杂度较高,达到双重指数级别,现有的工具如PRISM与MRMC均不支持对LTL性质的验证。针对这个问题,通过对原有的LTL概率模型检验算法进行优化,实现了一个高效的LTL概率模型检验工具。通过对比实验验证了该工具的有效性。     

Formal modeling,performance estimation,and model checking of wireless sensor network algorithms in Real-Time Maude

The purpose of this paper is to show how the rewriting-logic-based Real-Time Maude language and tool can be used to formally model, simulate, and model check advanced wireless sensor network (WSN) algorithms. This is done by first proposing some general techniques for modeling and analyzing WSN algorithms, and then by showing how these techniques have been applied to the modeling, performance estimation, and model checking of the state-of-the-art optimal geographical density control (OGDC) density control algorithm. Wireless sensor networks in general, and the OGDC algorithm in particular, pose many challenges to their formal specification and analysis, including novel communication forms, spatial entities, time-dependent and probabilistic features, and the need to analyze both correctness and performance. We focus on Monte Carlo simulations to evaluate the performance of OGDC. Extensive simulations with up to 800 sensor nodes, and comparison with the ns-2 simulations of OGDC, indicate that Real-Time Maude simulations provide fairly accurate performance estimates of WSN algorithms. As a consequence, simulating the high-level Real-Time Maude model of a WSN algorithm eliminates the need for implementing it on a simulation tool to get a faithful estimate of its performance, while providing much greater flexibility in defining the appropriate simulation scenario; in addition, Real-Time Maude model checking can search for “corner case” bugs and evaluate best-case and worst-case performance. Some of the techniques presented in this paper are also used in an ongoing analysis effort of another state-of-the-art WSN algorithm.     

使用模型检测解决概率布尔网络优化控制

系统生物学期望对复杂生物系统建立一个真实的、可计算的模型,以便于以系统的角度去理解生物系统的演变过程。在系统生物学中,一个重要的主题是通过外部的干预控制发展关于基因调控网络的控制理论,以作为未来基因治疗技术。目前,布尔网络及其扩展的概率布尔网络已经被广泛用于对基因调控网络进行建模。在控制问题的研究中,概率布尔控制网络的状态迁移本质上构成一条有限状态空间的离散时间马尔科夫决策过程。依据马尔科夫决策过程的理论,通过概率模型检测方法解决网络中有限范围优化控制问题和无限范围优化控制问题。针对带有随机干扰且上下文相关的概率布尔控制网络,使用概率模型检测器PRISM对其进行形式化建模,然后将两类优化控制问题描述为相应的时序逻辑公式,最后通过模型检测寻找出最优解。实验结果表明,提出的方法可以有效地用于生物网络的分析和优化控制。     

An analytical model for information retrieval in wireless sensor networks using enhanced APTEEN protocol

Wireless sensor networks are a new class of ad hoc networks that will find increasing deployment in coming years, as they enable reliable monitoring and analysis of unfamiliar and untested environments. The advances in technology have made it possible to have extremely small, low powered sensor devices equipped with programmable computing, multiple parameter sensing, and wireless communication capability. Because of their inherent limitations, the protocols designed for such sensor networks must efficiently use both limited bandwidth and battery energy. We develop an M/G/1 model to analytically determine the delay incurred in handling various types of queries using our enhanced APTEEN (Adaptive Periodic Threshold-sensitive Energy Efficient sensor Network protocol) protocol. Our protocol uses an enhanced TDMA schedule to efficiently incorporate query handling, with a queuing mechanism for heavy loads. It also provides the additional flexibility of querying the network through any node in the network. To verify our analytical results, we have simulated a temperature sensing application with a Poisson arrival rate for queries on the network simulator ns-2. As the simulation and analytical results match perfectly well, this can be said to be the first step towards analytically determining the delay characteristics of a wireless sensor network.     

一种物联网框架下传感节点间跳数与距离关系的研究

研究对数阴影衰落模型的无线传感器节点间跳数与距离关系的问题。随机部署在圆形区域内的节点位置服从Poisson分布,节点间自组织构成连通网络。借助于对数阴影衰落模型特征和节点分布规律,给出了已知节点间距的跳数概率分布表达式,同时考虑了多跳依赖问题对分布表达式的影响;基于贝叶斯公式,推导出已知跳数信息的距离分布关系,并进行了实验分析与验证。结果表明,理论的推导结论与实验统计结果具有较好的一致性。     

Symbolic model checking for channel-based component connectors

This paper introduces a temporal logic framework to reason about the coordination mechanisms and data flow of exogenous coordination models. We take a CTL-like branching time logic, augmented with regular expressions that specify the observable I/O-operations, as a starting point. The paper provides the syntax and semantics of our logic and introduces the corresponding model checking algorithm. The second part of the paper reports an implementation that relies on a symbolic representation of the coordination network and the connected components by means of binary decision diagrams. A couple of examples are given to illustrate the efficiency of the model checking techniques and their implementation.     

一种基于数据流跟踪的无线传感网能量模型及网络优化

提出了一种基于数据流跟踪的能量模型,通过跟踪数据流在网络中的整个过程来计算全网的能量消耗,是一种不受网络结构限制的普遍适用的能量模型;在此基础上.建立了基于能耗的网络优化模型,针对链式和簇式结构进行了拓扑、功率和路由方面的优化设计,仿真结果证明了理论分析的正确性.     

无线传感器网络最大生命期通信模型研究*

提出一种新的无线传感器网络最大生命期通信模型,研究了无线传感器网络中多源多链路多基站的最大生命期问题.为均衡数据流量分布,源节点产生的数据可以通过多条链路转发到多个基站.针对无线传感器网络能量和带宽受限等多约束条件,建立以网络最大生命期为最优目标和以降低节点处的数据量为次优目标的线性规划模型,依靠现有的分布式算法解决该模型.通过仿真实验验证了通信模型在多基站环境中的性能,并表明所提出的模型能够有效地延长网络生命期.     

Recent Advances in Real-Time Maude

This paper gives an overview of recent advances in Real-Time Maude. Real-Time Maude extends the Maude rewriting logic tool to support formal specification and analysis of object-based real-time systems. It emphasizes ease and generality of specification and supports a spectrum of analysis methods, including symbolic simulation, unbounded and time-bounded reachability analysis, and LTL model checking. Real-Time Maude can be used to specify and analyze many systems that, due to their unbounded features, such as unbounded data structures or dynamic object and message creation, cannot be modeled by current timed/hybrid automaton-based tools. We illustrate this expressiveness and generality by summarizing two case studies: (i) an advanced scheduling algorithm with unbounded queues; and (ii) a state-of-the-art wireless sensor network algorithm. Finally, we give some (often easily checkable) conditions that ensure that Real-Time Maude's analysis methods are complete, also for dense time, for object-based real-time systems. In practice, our result implies that Real-Time Maude's time-bounded search and model checking of LTL time-bounded formulas are complete decision procedures for a large and useful class of non-Zeno real-time systems that fall outside the scope of systems that can be modeled in decidable fragments of hybrid automata, including the sensor network case study discussed in this paper.     

基于概率模型检测和遗传算法的基因调控网络的无限范围优化控制

基因调控网络是一类基本且重要的生物网络,通过对其进行控制可以实现生物系统功能的调节。在生物系统中,通过外部的干预控制构造关于基因调控网络的控制理论成为了非常热门的研究主题。目前,作为一种重要的网络模型,带有干扰且上下文相关的概率布尔网络已经被广泛地应用于基因调控网络优化控制问题的研究中。针对无限范围的优化控制问题,文中提出了一种基于概率模型检测和遗传算法的近似最优控制策略的计算方法。首先,该方法将无限范围控制中定义的期望总成本归约为离散时间马尔科夫链上的平稳状态回报;然后,构建包含固定控制策略的带有干扰且上下文相关的概率布尔网络模型,采用带回报属性的时序逻辑公式表示固定控制策略的成本,采用概率模型检测器PRISM进行自动计算。进一步,采用遗传算法,将固定控制策略编码为遗传算法解空间中的个体,基于其控制成本,定义个体的适应度值,将PRISM作为求解器,通过在解空间上迭代地执行遗传操作获取近似最优解。将所提方法应用于WNT5A网络中,实验结果证明了该方法的有效性。     

对无线传感器网络区域数据聚合有效性的研究

通过抽象出无线传感器网络中区域数据回传的网络模型,定量研究了区域数据聚合的节能条件,证明了先聚合再回传比直接进行数据回传所节省的相对路径长度,如果大于等于数据相关性与源节点个数的比值时,区域数据聚合一定可以节省能耗,并进一步给出了当数据聚合点在网络的不同位置,或数据的空间相关性不同时,区域数据聚合的节能条件。对于无线传感器网络的部署、路由协议的选择及评估数据聚合算法的能量有效性等,均具有一定的参考价值。     

多因素信任的无线传感器网络信任模型

针对无线传感器网络中存在多种因素影响节点可信的问题,提出了节点路由向量阈;在基于信誉的信任管理框架(RFSN)模型的基础上,采用节点路由向量阈方法,建立了多因素信任的无线传感器信任模型。该模型综合利用通信信任、能量信任和路由向量信任来计算节点信任度,较客观真实地反映出节点的信任程度,应对无线传感器网络遇到的多种安全威胁。仿真实验表明,该模型能更准确地识别节点是否可信,可及早发现恶意节点,延长了网络生存期。     

Performance analysis of prioritized Automatic Repeat-request systems in the presence of self-similar traffic

Automatic Repeat reQuest (ARQ) is a promising forward error control mechanism for improving the reliability of data transmission over wireless channels. Traffic self-similarity has been discovered to be a ubiquitous phenomenon in communication networks with a significant impact on the network performance and user-perceived Quality-of-Service (QoS). However, due to the high complexity and challenges of modelling traffic self-similarity, there has not been any analytical model reported for ARQ under self-similar traffic. To fill this gap, we develop a novel analytical model of multi-buffer ARQ systems in the presence of prioritized self-similar traffic for reliable data transmission and QoS differentiation. This model can be used to investigate the probabilities of queueing loss and transmission loss in the multi-buffer ARQ systems. The validity of the analytical model is demonstrated via extensive comparison between analytical and simulation results. The model is further adopted to investigate the effects of service capacity and delay bound of ARQ on the system performance.     

TCP-Cherry for satellite IP networks: Analytical model and performance evaluation

TCP-Cherry is a novel TCP congestion control scheme that we devised for ensuring high performance over satellite IP networks and the alikes which are characterized by long propagation delays and high link errors. In TCP-Cherry, two new algorithms, Fast-Forward Start and First-Aid Recovery, have been proposed for congestion control. Our algorithms use supplement segments, i.e., low-priority segments to probe the available bandwidth in the network for the TCP connections along with carrying new data blocks. In this paper, we present our new congestion control scheme, TCP-Cherry and devise an analytical model for it. Our major contributions in this paper include the analytical model and equations for performance evaluation, validation of the analytical model through comparison between analytical and simulation results and devising a guideline to tune the buffer related parameters both at the sender as well as the receiver ends for optimum throughput performance. Experiments show that simulation results and the calculated throughput from our analytical model match quite closely, thereby verifying the appropriateness of the model. In addition, from analysis of simulation results, we discover that a buffer size at the receiver, rwnd, that is around four times maxcwnd, or the maximum congestion window at the sender side, is likely to maintain high throughput over a wide range of operating conditions.     

Bulk data dissemination in wireless sensor networks: Modeling and analysis

Wireless sensor networks (WSNs) have recently gained a great deal of attention as a topic of research, with a wide range of applications being explored. Bulk data dissemination is a basic building block for sensor network applications. The problem of designing efficient bulk data dissemination protocols has been addressed in a number of recent studies. The problem of accurately analyzing the performance of these protocols, however, has not been addressed sufficiently in the literature. In this work, we show a way of accurately analyzing the performance of bulk data dissemination protocols in WSNs. Our model can be applied to practical network topologies by use of the shortest propagation path. Our model is accurate by considering topological information, impact of contention, and impact of pipelining. We validate the analytical results through testbeds and detailed simulations. Results show that the analytical results fit well with the testbed results and simulation results. Further, we demonstrate that the analytical results can be used to aid protocol design for performance optimizations, e.g., page size tuning for shortening the completion time.     

Cluster Size Optimization in Sensor Networks with Decentralized Cluster-Based Protocols

Network lifetime and energy-efficiency are viewed as the dominating considerations in designing cluster-based communication protocols for wireless sensor networks. This paper analytically provides the optimal cluster size that minimizes the total energy expenditure in such networks, where all sensors communicate data through their elected cluster heads to the base station in a decentralized fashion. LEACH, LEACH-Coverage, and DBS comprise three cluster-based protocols investigated in this paper that do not require any centralized support from a certain node. The analytical outcomes are given in the form of closed-form expressions for various widely-used network configurations. Extensive simulations on different networks are used to confirm the expectations based on the analytical results. To obtain a thorough understanding of the results, cluster number variability problem is identified and inspected from the energy consumption point of view.     

A methodological approach for model validation in faster than real-time simulation

When successfully dealing with time constraints, faster than real-time simulation (FRTS) improves process control capabilities through providing short-term predictions. Validation of a simulation model is accomplished through comparing system observations and model data corresponding to the same time points. A methodological approach is necessary for the realization of this comparison, considering the time-dynamic system behaviour and the potential deviations between the model and the system. A seven-step method is proposed, emphasizing the following issues: determining when predictions should be considered as valid, accomplishing validation on the basis of the available model and system data, considering that not all deviations between the model and the system are of equal significance, and indicating potential system changes, so that the model can be modified in real time. Computer networks are used as an example domain, due to their multi-entity structure and time-dynamic behaviour, offering excellent test cases for evaluating the proposed method. Experimental FRTS results from the application of the proposed method to the network domain are also presented.     

车载自组织网络中的数据分发机制

车载自组织网络（vehicular ad-hoc network,简称VANET）作为一种新型的移动自组织网络,应用前景广阔.鉴于长距离数据分发机制是支撑VANET应用的一个不可或缺的机制,提出了一种VANET下路边单元（roadsideunit,简称RSU）辅助的数据分发机制Ara,并在不同的交通场景下对其性能进行了评估.实验结果表明,即使在有RSU出现故障的情况下,Ara也可以保证较高的数据到达率、较小的延迟和较低的消息开销.同时,通过建立分析模型对Ara的数据传递延迟进行了理论分析.该分析模型建立在车辆的微观流模型之上,可以推导出不同RSU 部署场景下的数据传递延迟.模拟实验结果验证了模型的正确性,因此该分析模型可以对Ara数据传递的性能进行预测.     

Optimal energy allocation in heterogeneous wireless sensor networks for lifetime maximization

We consider the problem of optimal energy allocation and lifetime maximization in heterogeneous wireless sensor networks. We construct a probabilistic model for heterogeneous wireless sensor networks where sensors can have different sensing range, different transmission range, different energy consumption for data sensing, and different energy consumption for data transmission, and the stream of data sensed and transmitted from a sensor and the stream of data relayed by a sensor to a base station are all treated as Poisson streams. We derive the probability distribution and the expectation of the number of data transmissions during the lifetime of each sensor and the probability distribution and the expectation of the lifetime of each sensor. In all these analysis, energy consumption of data sensing and data transmission and data relay are all taken into consideration. We develop an algorithm to find an optimal initial energy allocation to the sensors such that the network lifetime in the sense of the identical expected sensor lifetime is maximized. We show how to deal with a large amount of energy budget that may cause excessive computational time by developing accurate closed form approximate expressions of sensor lifetime and network lifetime and optimal initial energy allocation. We derive the expected number of working sensors at any time. Based on such results, we can find the latest time such that the expected number of sensors that are still functioning up to that time is above certain threshold.