在无线传感器网络中应用虚拟骨干，可以有效地节约能量、减少干扰、延长网络寿命，在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展，侧重于研究方法和理论结果，为相关研究人员提供参考.

In a network system, a propagated failure (PF) is a failure originating from a network component that can cause extensive damages to other network components or even the failure of the entire system. Existing works on PFs have mostly assumed the deterministic effect from a component PF, i.e., a fixed subset of system components is affected whenever the PF occurs. However, in many real-world systems, the components may have different levels of protection, and the effect of damage from a component PF can be dependent upon the status of other components within the same system or the occurrence order of component failures. This paper proposes a new analytical method based on multi-valued decision diagrams (MDDs) for the reliability analysis of network systems with dependent propagation effects. Particularly, new MDD modeling procedures are proposed for considering different types of dependent PF effects introduced by different protection levels. After the system MDD is generated using a new MDD combination algorithm to efficiently handle the dependent PF effects, methods for computing the network reliability and component importance measures are presented. The detailed analysis of an example network system subjected to dependent PFs is presented to illustrate the basics and application of the proposed method. It is shown that the proposed MDD-based method generates smaller model size and thus presents lower computational complexity in the model generation and evaluation than the existing Markov method and separable method.

Modern computing systems typically use a large number of independent, non-identical computing nodes to perform a set of coordinated computations in parallel. The computing system and its constituent computing nodes often exhibit more than two performance levels or states corresponding to different computing powers. This paper models and evaluates performability of largescale multi-state computing systems, which is the probability that a computing system performs at a particular performance level. The heterogeneity in the constituent components of different nodes (due to factors such as different model generations, model suppliers, and operating environments) makes performability analysis difficult and challenging. In this paper a specification method for system performance level (SPL) is first introduced. A multi-valued decision diagram (MDD) based approach is then proposed for performability analysis of multi-state computing systems consisting of nodes with different state occupation probabilities, which encompasses novel and efficient MDD model generation procedures. Example and benchmark studies are performed to show that the proposed approach can offer efficient performability analysis of large-scale computing systems.

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m ≥ k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 ≤ k ≤ 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (α+5ρ) fork ≥ 3 and (α+2.5ρ) for k = 2, where α is the performance ratio for the minimum weight m-fold dominating set problem and ρ is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).

To save energy and alleviate interference, connected dominating set (CDS) was proposed to serve as a virtual backbone of wireless sensor networks (WSNs). Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a k-connected m-fold dominating set (abbreviated as (k, m)-CDS) problem. A node set C ⊆ V (G) is a (k, m)-CDS of graph G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. Constant approximation algorithm is known for (3, m)-CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for (3, m)-CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at most γ, where γ = α + 8 + 2 ln(2α - 6) for α ≥ 4 and γ = 3α +2 ln 2 for α <; 4, and α is the performance ratio for the minimum (2, m)-CDS problem. Using currently best known value of α, the performance ratio is ln δ +o(ln δ), where δ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. Applying our algorithm on a unit disk graph, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the (3, m)-CDS problem on a unit disk graph.

The User Authorization Query (UAQ) Problem is a key issue related to efficient handling of users’ access requests in Role Based Access Control (RBAC) systems. However, there may not exist any solution to a given UAQ problem due to the limitation caused by the current system state, because missing any requested permission may thwart a task, while an extra permission may bring an intolerable risk to the system. Hence, update of the role–permission assignment is needed to support the feasibility of an UAQ problem. In this paper, we study fundamental problems related to role–permission reassignment, including the RVP problem the goal of which is to determine whether a given role–permission assignment satisfies all reassignment objectives and does not violate any prerequisite constraint or permission-capacity constraint, the RFP problem which verifies whether there exists a valid role–permission assignment, and the RGP problem which studies how to generate a valid role–permission assignment. We present the computational complexity analysis of RVP, RFP and RGP, showing that RVP is solvable in linear time, while both RFP and RGP are NP-hard. We also propose an approach for RGP, which incorporates a preprocessing to decrease the size of the problem, and reduce it to an SAT problem. Finally, experimental results show the validity and effectiveness of our proposed approach.

Despite the increasing popularity and successful examples of crowdsourcing, its openness overshadows important episodes when elaborate sabotage derailed or severely hindered collective efforts. A service exchange dilemma arises when non-cooperation among self-interested users, and zero social welfare is obtained at myopic equilibrium. Traditional rating protocols are not effective to overcome the inefficiency of the socially undesirable equilibrium due to specific features of crowdsourcing: a large number of anonymous users having asymmetric service requirements, different service capabilities, and dynamically joining/leaving a crowdsourcing platform with imperfect monitoring. In this paper, we develop the first game-theoretic design of the two-sided rating protocol to stimulate cooperation among self-interested users, which consists of a recommended strategy and a rating update rule. The recommended strategy recommends a desirable behavior from three predefined plans according to intrinsic parameters, while the rating update rule involves the update of ratings of both users, and uses differential punishments that punish users with different ratings differently. By quantifying necessary and sufficient conditions for a sustainable social norm, we formulate the problem of designing an optimal two-sided rating protocol that maximizes the social welfare among all sustainable protocols, provide design guidelines for optimal two-sided rating protocols and a low-complexity algorithm to select optimal design parameters in an alternate manner. Finally, illustrative results show the validity and effectiveness of our proposed protocol designed for service exchange dilemma in crowdsourcing.

A vertex set F is a k-path vertex cover () of graph G if every path of G on k vertices contains at least one vertex from F. A graph G is a d-dimensional ball graph if each vertex of G corresponds to a ball in , two vertices are adjacent in G if and only if their corresponding balls have nonempty intersection. The heterogeneity of a ball graph is defined to be , where and are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum problem in a ball graph whose heterogeneity is bounded by a constant.

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (VCPk) has received a lot of attention in recent years. Given a graph G=(V,E), a vertex set C⊆V is a k-path vertex cover (VCPk) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (CVCPk) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for MinCVCPk on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.

For a connected graph , an edge set is a k-restricted-edge-cut, if is disconnected and every component of has at least k vertices. The k-restricted-edge-connectivity of G, denoted by , is defined as the cardinality of a minimum k-restricted-edge-cut. The k-isoperimetric-edge-connectivity is defined as , where is the set of edges with one end in U and the other end in ⧹. In this note, we give some degree conditions for a graph to have optimal and/or .