双环网络直径的对称性及应用

双环网络是计算机互连网络、大规模并行处理系统和通讯系统的一类重要拓扑结构。双环网络有效性的一个重要参数是信息的传输延迟,它可以用其图的直径来度量。文中从双环网络的图论模型出发,证明了双环网络中一个被广泛关注的问题,即双环网络直径的对称性,并给出了一些应用。     

双环网络直径的对称性及应用

双环网络是计算机互连网络、大规模并行处理系统和通讯系统的一类重要拓扑结构。双环网络有效性的一个重要参数是信息的传输延迟，它可以用其图的直径来度量。文中从双环网络的图论模型出发，证明了双环网络中一个被广泛关注的问题，即双环网络直径的对称性，并给出了一些应用。     

双环网络直径的对称性及其仿真算法

双环网络有效性的一个重要参数是信息的传输延迟,它可以用其图的直径来度量.从双环网络的图论模型出发,首次使用矩阵原理证明了双环网络直径的对称性,根据对称性,使搜寻最优或紧优G(N;s)的范围可以减少一半;给出了双环网络直径的仿真算法;并利用C#作为编程语言、SQL Server2000作为数据库实现了该算法.     

有向双环网和无向双环网直径规律的对比

近年内双环网络越来越广泛地被应用于局域网中.目前得到广泛的认同的是双环网络最小直径的几种求解方法,即是指对于任意给定N,而2≤S≤N-1的这样一族双环网络中找到任意节点对间的最小距离中的最大者.在可以轻松计算出双环网络直径以后,文中将给出一个新的行之有效的算法来比较有向双环网和无向双环网直径的规律.     

双环Petersen网络直径公式及最优路由算法

双环Petersen图互联网络DLCPG(k)是双环网络与Petersen图的笛卡尔积,它具有良好的可扩展性、较短的网络直径和简单的拓扑结构等特性。通过研究其拓扑结构,得到了DLCPG(k)直径的显式公式,并给出了该网络的最优单播路由算法。     

双优双环网络G(N; 1, s)的分布仿真

在直角坐标系下的一族有向双环网络 中,研究双优双环网络 的L形图形特征及其分布特性。该网络的直径、平均距离均达到最小值。计算4≤N≤1 000中任意N存在的双优双环网络个数 ,仿真4≤N≤1 000的n-N紧优分布图,发现n-N分布呈现平稳的波动特性, 不随 递增。     

无向双环网络G(N;±1,±s)的直径求解算法

提出无向双环网络G(N;±1,±s)的直径求解算法,利用VB6.0作为编程语言、SQLServer2000作为数据库来实现这一算法,对任意给定N,而2≤s≤N-1的这样一族无向双环网络的直径都可以计算出来,结果存入数据库,并且利用VB6.0的控件MSChart来模拟显示计算结果。找出了该族无向双环网络直径的分布特点:具有最大值、最小值和中间对称性;对任意N,有不少s使得G(N;±1,±s)紧优或几乎紧优。验证了Boesch和Wang等提出的无向双环网络G(N;±1,±s)的直径下界,给出了一个新的直径上界公式。     

无向双环网络G(N;±1,±s)的直径求解算法

提出无向双环网络G(N;±1,±s)的直径求解算法,利用VB6.0作为编程语言、SQL Server2000作为数据库来实现这一算法,对任意给定N,而2≤s≤N-1的这样一族无向双环网络的直径都可以计算出来,结果存入数据库,并且利用VB6.0的控件MSChart来模拟显示计算结果.找出了该族无向双环网络直径的分布特点:具有最大值、最小值和中间对称性;对任意N,有不少s使得G(N;±1,±s)紧优或几乎紧优.验证了Boesch和Wang等提出的无向双环网络G(N;±1,±s)的直径下界,给出了一个新的直径上界公式.     

双环网络存取控制的参量分析

本文通过数学分析,导出双环网络采用最快访问信道方式与最短路径方式的主要工作特性参量的计算公式,并举出典型实例,对上述两种存取控制方式作定性比较。     

无向双环网络G（N；±1，±s）的直径求解改进算法

利用计算机算法研究无向双环网络直径在国内外文献中尚不多见，文献[1]中提出了一种算法，并成功实现，其不足之处是利用数据库存取中间结果，严重影响了计算速度，当N值很大时需要计算的时间过长。针对这一不足，提出利用数组取代数据库来存取中间结果的改进算法。实验结果表明该算法较文献[1]算法极大地提高了运算速度，并列出了两个N大值直径分布图。     

特征相关的结构化P2P结点编址和数据副本分发

传统结构化P2P网络中,随机或顺序产生结点标识,结点分布与结点位置、安全性等特征间缺乏相关性,无法有效应对"错误相关"现象,存在数据丢失的风险。提出一种新的编址方法和相关联的副本分发算法,该算法将结点的位置、安全性等特征信息融入到结点标识中,使结点按特征分布,在副本分发过程中依据标识来识别结点特征,避开或靠近具有特定特征的结点,解决错误等问题,提高分发效率。仿真实验给出了改进后的结点分布和备份点选择结果,表明了方法的有效性。     

Avoiding Energy Holes in Wireless Sensor Networks with Nonuniform Node Distribution

In this paper, we investigate the theoretical aspects of the nonuniform node distribution strategy used to mitigate the energy hole problem in wireless sensor networks (WSNs). We conclude that in a circular multihop sensor network (modeled as concentric coronas) with nonuniform node distribution and constant data reporting, the unbalanced energy depletion among all the nodes in the network is unavoidable. Even if the nodes in the inner coronas of the network have used up their energy simultaneously, the ones in the outermost corona may still have unused energy. This is due to the intrinsic many-to-one traffic pattern of WSNs. Nevertheless, nearly balanced energy depletion in the network is possible if the number of nodes increases in geometric progression from the outer coronas to the inner ones except the outermost one. Based on the analysis, we propose a novel nonuniform node distribution strategy to achieve nearly balanced energy depletion in the network. We regulate the number of nodes in each corona and derive the ratio between the node densities in the adjacent (i + 1)th and ith coronas by the strategy. Finally, we propose (q-switch routing, a distributed shortest path routing algorithm tailored for the proposed nonuniform node distribution strategy. Extensive simulations have been performed to validate the analysis.     

无线传感器网络中节点非均匀分布的能量空洞问题

节点非均匀分布策略能缓解无线传感器网络中的能量空洞问题.文中从理论上探讨这种策略,证明在节点非均匀分布的圆形网络中,如果节点持续向Sink节点发送数据,能量空洞现象将无法避免,而当节点数目满足一定关系时,网络中能够实现次优能耗均衡.文中提出一种节点非均匀分布策略及相应的路由算法用于实现这种次优能耗均衡.模拟结果显示网络生存周期终止时,处于网络内部的节点几乎达到了能耗均衡.     

负载相似节点分布解决传感器网络能量洞问题

基于多跳路由的传感器网络,靠近sink的节点由于要转发更多的数据,其能量消耗较快.能量消耗的不平衡导致了sink周围产生能量洞(energy hole),造成能量浪费,远离sink的节点还有大量的能量,但产生的数据不能传送到sink.研究了传感器网络的能量洞问题.在网络的连续空间状态下分析节点的负载分布特性,并研究空闲侦听(idle listening)对能量消耗的影响.基于分析结果,提出负载相似节点分布(load-similar node distribution)策略,即根据负载分布特性配置节点,负载重的区域配置较多的节点,以平衡各区域节点的能量消耗,解决能量洞问题.仿真结果显示,在不考虑空闲侦听能量消耗的情况下,与已有的一种非均匀节点分布和均匀节点分布相比,负载相似节点分布策略对网络寿命有显著改善;当考虑空闲侦听时,由于空闲侦听的能量消耗在总能量消耗中占较大比重,影响了网络寿命,但与其他两种节点分布策略相比,负载相似节点分布对网络寿命仍然有所改善.该分析模型和提出的负载相似节点分布策略可适用于其他多跳传感器网络.     

自组网中节点分布对网络连通度的影响分析

本文通过对不同网络规模的自组网中节点分布密度与网络连通性关系的研究分析，为在自组网的网络规划中选择与网络规模相适合的满足网络连通性要求的网络覆盖范围，从而提高网络容量，提供一种有效的设计方法。     

基于差分蜂群算法的无线传感器网络节点分布优化

针对无线传感器网络节点分布优化问题,在保证节点间相互连通的情况下建立节点分布优化模型,提出了一种有效的差分蜂群优化算法,从而实现了同构无线传感器网络节点对目标区域的高效覆盖。改进算法将差分进化操作引入蜂群算法中雇佣蜂的搜索方式,以提高雇佣蜂搜索的多样性和避免计算量的浪费。差分蜂群算法在无线传感器网络节点分布优化问题上进行了测试,并与差分进化、人工蜂群两种算法进行了仿真对比。从3种算法的网络覆盖率迭代曲线可以看出,差分蜂群算法整体的探索能力及收敛速度较之其他2种算法都有所提升。除此之外,3种算法对无线传感器网络覆盖优化问题进行了100次试验,覆盖率统计结果进一步验证了所提算法的有效性。     

On the Bisection Width and Expansion of Butterfly Networks

This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n -input butterfly network is without wraparound, and n with wraparound. The former result is surprising, since it contradicts the prior ``folklore' belief that the bisection width is n . We also show that every set of k nodes has at least (k/(2 log k))(1-o(1)) neighbors in a butterfly without wraparound, and at least (k/log k)(1-o(1)) neighbors in a butterfly with wraparound, if k is and o(n) , respectively. Received September 30, 1997, and in final form July 30, 2001. Online publication November 23, 2001.     

The Diameter and Average Distance of Supertoroidal Networks

The subject of this paper is a family of network topologies which are intended to be practical enough to be implemented in a parallel computer using contemporary technology. These network topologies offer an alternative to the three-dimensional mesh or toroid and are most likely to be useful for a network with between 512 and 16,384 nodes. The topologies, which are called supertoroids, are Cayley graphs of groups. The groups are semidirect products of two cyclic groups, one of order ck and the other of order c²l. The resulting Cayley graph has c³kl vertices and is of degree 4. The main results of this paper are two theorems. The first states that the diameter of the supertoroidal network with c³kl nodes is [cl/2] + [ck/2] if c ≥ 8. The second states that the average distance is asymptotically (in c) equal to ([cl/2] + [ck/2])/2. Because of these facts, the supertoroidal network has latency which is lower than the latency of a three-dimensional toroid of the same size. Although the proofs of these theorems are a tour-de-force of arithmetic in the underlying group, they are based upon exploitation of parallelism of paths in a Cayley graph.     

Sorting and Counting Networks of Arbitrary Width and Small Depth

We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let w be the product w = p ₀ ⋅ p ₁ ⋅s p _n-1 , whose factors are not necessarily prime. We present a novel network construction of width w and depth O(n ² ) = O(log ² w) , using comparators (or balancers) of width less than or equal to max(p _i ) . This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width w , one for each distinct factorization of w . A factorization in which max(p _i ) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(p _i ) is small and n is large makes the opposite tradeoff. Received June 18, 2001. Online publication October 30, 2001.     

无线传感器网络节点定位技术

对无线传感器网络定位技术进行了深入的探讨,从WSN节点的定位机制、定位算法的分类、已有的定位算法及算法性能的评价标准等方面进行分析,并对比了质心定位算法、DV-Hop算法、凸规划定位算法、APIT算法等几种经典的方法。结果表明：各种算法在不同的应用环境下所表现的性能差别较大,没有哪种算法是最优的,应根据最感兴趣的性能指标选择合适的算法。最后提出了无线传感器网络节点定位技术需要解决的问题和研究方向。