A distributed approach to node clustering in decentralized peer-to-peer networks

Connectivity-based node clustering has wide-ranging applications in decentralized peer-to-peer (P2P) networks such as P2P file sharing systems, mobile ad-hoc networks, P2P sensor networks, and so forth. This paper describes a connectivity-based distributed node clustering scheme (CDC). This scheme presents a scalable and efficient solution for discovering connectivity-based clusters in peer networks. In contrast to centralized graph clustering algorithms, the CDC scheme is completely decentralized and it only assumes the knowledge of neighbor nodes instead of requiring a global knowledge of the network (graph) to be available. An important feature of the CDC scheme is its ability to cluster the entire network automatically or to discover clusters around a given set of nodes. To cope with the typical dynamics of P2P networks, we provide mechanisms to allow new nodes to be incorporated into appropriate existing clusters and to gracefully handle the departure of nodes in the clusters. These mechanisms enable the CDC scheme to be extensible and adaptable in the sense that the clustering structure of the network adjusts automatically as nodes join or leave the system. We provide detailed experimental evaluations of the CDC scheme, addressing its effectiveness in discovering good quality clusters and handling the node dynamics. We further study the types of topologies that can benefit best from the connectivity-based distributed clustering algorithms like CDC. Our experiments show that utilizing message-based connectivity structure can considerably reduce the messaging cost and provide better utilization of resources, which in turn improves the quality of service of the applications executing over decentralized peer-to-peer networks.     

Strategic Pricing in Next-Hop Routing with Elastic Demands

We consider a model of next-hop routing by self-interested agents. In this model, nodes in a graph (representing ISPs, Autonomous Systems, etc.) make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, and routing decisions of which downstream neighbors to forward traffic to (i.e., choosing the next hop). Traffic originates at a subset of these nodes that derive a utility when the traffic is routed to its destination node; the traffic demand is elastic and the utility derived from it can be different for different source nodes. Our next-hop routing and pricing model is in sharp contrast with the more common source routing and pricing models, in which the source of traffic determines the entire route from source to destination. For our model, we begin by showing sufficient conditions for prices to result in a Nash equilibrium, and in fact give an efficient algorithm to compute a Nash equilibrium which is as good as the centralized optimum, thus proving that the price of stability is 1. When only a single source node exists, then the price of anarchy is 1 as well, as long as some minor assumptions on player behavior is made. The above results hold for arbitrary convex pricing functions, but with the assumption that the utilities derived from getting traffic to its destination are linear. When utilities can be non-linear functions, we show that Nash equilibrium may not exist, even with simple discrete pricing models.     

基于多局域的恐怖组织网络择优增长演化模型

恐怖组织网络是一种特殊的复杂网络,其时空演化规律反映出恐怖组织活动的特征.为更准确地理解恐怖组织网络的动态演化规律,提出一种基于多局域的恐怖组织网络择优增长演化模型,并对此模型进行了仿真与模拟.该模型能准确地描述在局部信息条件下,新节点的择优和网络的增长过程及其规律;并且利用网络信息中心度来衡量恐怖组织网络节点的信念水平,动态地刻画了恐怖组织网络的增长过程.实验结果表明:恐怖组织网络的局域度分布仍服从幂律分布,网络信息中心度具有集中与分散性的特征;最后,对多个恐怖组织网络按该模型进行仿真演化,验证了该模型的准确性与科学性.     

基于弹簧模型的重要节点排序算法

重要节点排序是复杂网络研究的重要问题。用网络的鲁棒性和脆弱性指标评价基于引力模型的重要节点排序算法GM（gravity model）和其局部算法LGM（local gravity model）时,当度大的节点从网络中移除后,其引力较大的近邻节点的后续移除通常并不能在很大程度上影响网络的结构与功能,说明算法在重要节点排序精度方面仍然存在提升之处。基于此,在弹簧模型的启发下,进一步考虑网络节点近邻和路径信息,并结合网络直径,提出了重要节点排序算法SM（spring model）和其局部算法LSM（local spring model）。基于合成网络和真实网络数据集针对网络的鲁棒性和脆弱性与经典算法进行对比实验,结果表明SM算法和LSM算法对于网络中重要节点排序具有更高的准确性。特别地,在Power网络上的SIR传播实验进一步证明了SM算法相较于其他算法,具有更高的合理性和有效性。     

一种基于网络拓扑重合度的关键节点识别方法

关键节点识别是分析和掌握复杂网络结构和功能的重要手段,对于研究网络鲁棒性、维持网络稳定性具有重大现实意义.为了探索节点与邻居之间的关联性,提出了一种有关度中心性和公共邻居数量的关键节点识别方法,仅用局部信息就表征出了节点重要性,展现了网络拓扑重合度对关键节点识别的影响,网络拓扑重合度是指节点在通信过程中与其他节点可共用的部分.通过静态和动态攻击的方式对六个真实网络和三个人工网络进行节点移除攻击,以最大连通子图比例和网络效率作为节点识别准确性评价标准.实验表明蓄意攻击比随机攻击更有针对性,此外证明了所提方法与度中心性DC、K-shell分解法、映射熵ME方法、集体影响CI方法以及潜在增益EPG方法相比更能准确评估出节点的重要性.     

Ad Hoc入侵检测监视节点的自适应选择算法

提出一种监视节点基于事件触发机制的自适应选择算法(ETBAS),引入监视节点的监视状态,通过事件触发使非监视节点进入唤醒状态进行入侵检测,或使监视节点进入睡眠状态停止入侵检测。触发事件包括相邻节点的推选、节点能源低于某个阈值、网络拓扑结构的变化等。ETBAS具有自适应性,无论监视节点离开网络还是新节点进入网络,通过与相邻节点的信息交互,都能实现局部网络监视节点的自动更新。     

Randomized algorithms for stability and robustness analysis of high-speed communication networks

This paper initiates a study toward developing and applying randomized algorithms for stability of high-speed communication networks. The focus is on congestion and delay-based flow controllers for sources, which are "utility maximizers" for individual users. First, we introduce a nonlinear algorithm for such source flow controllers, which uses as feedback aggregate congestion and delay information from bottleneck nodes of the network, and depends on a number of parameters, among which are link capacities, user preference for utility, and pricing. We then linearize this nonlinear model around its unique equilibrium point and perform a robustness analysis for a special symmetric case with a single bottleneck node. The "symmetry" here captures the scenario when certain utility and pricing parameters are the same across all active users, for which we derive closed-form necessary and sufficient conditions for stability and robustness under parameter variations. In addition, the ranges of values for the utility and pricing parameters for which stability is guaranteed are computed exactly. These results also admit counterparts for the case when the pricing parameters vary across users, but the utility parameter values are still the same. In the general nonsymmetric case, when closed-form derivation is not possible, we construct specific randomized algorithms which provide a probabilistic estimate of the local stability of the network. In particular, we use Monte Carlo as well as quasi-Monte Carlo techniques for the linearized model. The results obtained provide a complete analysis of congestion control algorithms for internet style networks with a single bottleneck node as well as for networks with general random topologies.     

拍卖博弈模型在无线传感器网络路由中的应用研究

为了提高无线传感器网络数据转发的可靠性及能量利用率,本文基于拍卖博弈建立了拍卖路由博弈模型,并提出一种进行转发节点选择的价格路由博弈算法.在算法中潜在的转发节点为了从发送节点获得虚拟货币而相互竞争,发送节点根据各个转发节点的标价选择最佳转发节点.实验仿真表明拍卖路由博弈模型的合理、有效,提出的价格路由博弈算法能够降低节点的能量消耗,延长网络的生命周期.     

基于GSO算法的最小连通支配集问题求解

经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。