目的:只允许同级拖动。

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

采用步步逼近的方式构造问题的解,其下一步的选择总是在当前看来收效最快和效果最明显的那个。

两个判断:

  无线传感器网络的许多应用要求节点知道自身的位置信息,才能向用户提供有用的检测服务。没有节点位置信息的监测数据在很多场合下是没有意义的。比如,对于森林火灾检测、天然气管道监测等应用,当有事件发生时,人们关心的一个首要问题就是事件发生在哪里,此时如果只知道发生了火灾却不知道火灾具体的发生地点,这种监测没有任何实质的意义,因此节点的位置信息对于很多场合是至关重要的。

使用前提: 验证贪心模式的有效性

1.原节点(假设为:S)的父级如果不等于目标节点(假设为:T)的父节点,那么发生了跨级,即非同级移动。这个判断很容易。

  在许多场合下,传感器节点被随机部署在某个区域,节点事先无法知道自身的位置,因此需要在部署后通过定位技术来获取自身的位置信息。目前最常见的定位技术就是GPS(Global
Positioning
System)了,它能够通过卫星对节点进行定位,并且能够达到比较高的精度。因此要想对传感器节点进行定位,最容易想到的方法就是给每个节点配备一个GPS接收器,但是这种方法不适用于传感器网络,主要原因有以下几点:

最小生成树(minimum spanning tree)

输入:无向图G=(V, E); 边权重w(e)
输出:树T=(V, E’),

其中![](http://latex.codecogs.com/svg.latex?E’
\subseteq E),
使得权重![](http://latex.codecogs.com/svg.latex?weight(T))
= \sum_{e \in E’} w_e)

2.S、T是同一级的,但是S是移动到T下一级,这种情景下,移动过程中,S和T的父节点是一致的,不能判断是否跨级移动,那么怎么办判断呢?

  1)GPS接收器通常能耗高,而对于无线传感器网络中的节点来说,一般能耗很有限,给每个节点配备一个GPS接收器会大大缩短网络寿命;

树的性质
  1. 具有n个节点的树的边数为n-1
  2. 一个无向图是树,当且仅当任意两个节点间仅存在唯一路径

方案1:在afterDrop事件中来判断父节点是否一致,因为移动已经完成,父节点发什么了变化,根据判断结果然后再把节点恢复回去。这种做法很low。

  2)GPS接收器成本比较高,给无线传感器网络中的每个节点配备一个GPS接收器,需要投入很大成本,尤其对于大规模的无线传感器网络来说不是很适合;

Kruskal算法

不断地重复地选择未被选中的边中权重最轻而且不会形成环的一条。

procudure kruskal
for all u in V:
    makeset(u)
sort the edges E by weight
for all edges {u, v} in E, in increasing order of weight:
    if find(u) != find(v)
        add edge {u,v} to X
        union(u, v)
  • makeset(x): 创建一个仅包含x的独立集合
  • find(x): x属于哪个集合?
  • union(x, y): 合并包含x和y的集合
    共需要|V|次makeset + 2|E|次find + |V|-1次union操作

find操作不一定成功触发union操作,因此最坏情况下会需要2|E|次

数据结构:有向树
集合中的顶点对应树的节点,每个节点包含一个父指针,一级级指向树根。树根的父指针指向该元素自身。

必发娱乐官方网站 1

有向树

node

  1. p //父节点指针
  2. rank //该节点下悬挂的子树高度
  • 方案一
    合并时让较低的树的根指向较高的树的根(基于等级的合并)

  procedure makeset(x)
    p(x) = x
    rank(x) = 0
  procedure find(x)
    while(x != p(x))
        x = p(x)
    return x
  procedure union(x, y)
    rx = find(x), ry = find(y)
    if rx == ry return
    if rank(rx) > rank(ry)
        p(ry) = rx
    else if rank(rx) == rank(ry)
        p(rx) = ry
        rank(ry) += 1
    else
        p(rx) = ry
  • 方案二
    路径压缩:
    循着一系列的父指针最终找到树根后,改变所有这些父指针的目标,使其直接指向树根

  procedure find(x)
    while(x != p(x))
        p(x) = find(p(x))
    return x

find中rank未进行更新,此时rank的含义无法解释为子树的高度。
此时有向树的高度不会超过2。

  • 方案三
    我们可以发现find和union操作均只关心树的顶层,是否可以直接使用树高为2的有向树呢?并在union()操作中,对于两个树高为2的有向树,进行其中一棵的压缩。

但仔细分析可以得出,此方案与方案二本质相同,仅将find()操作总共所做的工作转移到union()操作中。

方案序号 makeset find union 该部分效率
1 O(1) O(logn) O(logn) (V+E)logn
2 O(1) > O(1) > O(1) V+E

方案2如何平摊分析?TODO
总时间复杂度为T(sort)和T(find/union)中较大的那个

see java implement:
greedy.mst.KruskalMST

方案2:在移动过程中判断S被移动到T节点的位置:T节点前、T节点后、T节点下,如果是移动到T节点下,那么禁止移动即可。

  因此有必要研究适合无线传感器网络的定位技术。下面分两个部分来介绍节点定位的相关研究:1)节点定位的基本概念;2)节点定位的基本思路;3)常见算法。

Prim算法

算法中间阶段的边集X构成一个子树,该子树顶点的集合表示为S。我们选择S中顶点与S外顶点之间的最轻边加入X,即以最小代价将所有原本不属于S的顶点包含进来。

与Dijkstra的关系
伪代码基本一致,区别体现在优先队列排序使用的键值

  • Prim: 键值为节点与集合S中顶点间的最轻边的权重;
  • Dijkstra:键值为节点到起始点的完整路径长度;

pseudocode如下:

procedure prim
for all u in V
    dist(u) = \infty
    pre(u) = nil

dist(s) = 0
PQ = makequeue(V) (using dist-values as keys)
while PQ is not empty
    u = deletemin(PQ)
    for all edges (u, v) in E
        if dist(v) > l(u, v)
            dist(v) = l(u, v)
            pre(v) = u
            decreasekey(PQ, v)

可以看到仅是dist(u)+l(u, v)变为l(u, v)

see java implement:
greedy.mst.PrimMST

下面贴出方案2判断方法:

一.节点定位的基本概念

哈夫曼编码
  • 编码压缩

压缩比越高,随机性越低,可预测性越好

  • 无前缀特性,任一个码字都不应该是其他码字的前缀

无前缀编码中每个字符对应于树中的一个叶节点

procedure Huffman(f)
Input: An array f[1...n] of frequencies
Output: An encoding tree with n leaves

let H be a priority queue of integers, ordered by f
for i = 1 to n: insert(H, i)
for k = n + 1 to 2n -1
    i = deletemin(H), j = deletemin(H)
    create a node numbered k with children i,j
    f[k] = f[i] + f[j]
    insert(H, k)

编码输出

call print(root, 1)

print(node, num) {
  if node is null return
  print node's code based on num
    :num to binary and then remove the head '1'
  print(node.left, 2*num)
  print(node.right, 2*num + 1)
}

see implement:
greedy.Huffman

 

  无线传感器网络中的节点定位是指传感器节点根据网络中少数已知节点的位置信息,通过一定的定位技术确定网络中其他节点的位置信息的过程。

其他
/// <summary>
        /// 获取拖动过程中的方向
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        /// <returns></returns>
        private DragInsertPosition AjustDirection(object sender, DragEventArgs e)
        {
            TreeListNode dragNode, targetNode;
            TreeList tl = sender as TreeList;
            Point p = tl.PointToClient(new Point(e.X, e.Y));
            dragNode = e.Data.GetData(typeof(TreeListNode)) as TreeListNode;
            TreeListHitInfo hit = tl.CalcHitInfo(p);
            PropertyInfo pi = typeof(TreeList).GetProperty("Handler", BindingFlags.Instance | BindingFlags.NonPublic);
            TreeListHandler handler = (TreeListHandler)pi.GetValue(tl, null);
            return handler.StateData.DragInfo.DragInsertPosition;

        }

 private void treeListNav_DragOver(object sender, DragEventArgs e)
        {
            TreeListNode dragNode = e.Data.GetData(typeof(TreeListNode)) as TreeListNode;
            System.Diagnostics.Debug.WriteLine("Over:" + e.Effect);
            TreeListNode targetNode;
            Point p = treeListNav.PointToClient(MousePosition);
            targetNode = treeListNav.CalcHitInfo(p).Node;
            if (targetNode == null)
            {
                return;
            }
            FileContent tagParent = null;//拖动后的父级数据
            if (targetNode.ParentNode != null)
            {
                tagParent = this.treeListNav.GetRow(targetNode.ParentNode.Id) as FileContent;
            }
            if (sourceParent != tagParent)//发生跨级拖动
            {
                // MessageHelper.ShowHit("只能在同一级拖动,移动未成功。");
                e.Effect = DragDropEffects.None;
                return;
            }

            //移动到了同级子节点下
            if (AjustDirection(sender, e) == DragInsertPosition.AsChild)
            {
                e.Effect = DragDropEffects.None;                
                return;
            }

            if (e.Effect == DragDropEffects.Link)
            {
                //     MessageHelper.ShowHit("不能移动到子集。");
                e.Effect = DragDropEffects.None;
            }


        }

  在无线传感器网络中节点通常可以分为信标节点(beacon node or anchor
node)和未知节点(unknown
node),其中信标节点也称为锚节点或者参考点,未知节点也称为普通节点。信标节点是位置信息已知的节点,未知节点是未知信息未知的节点。信标节点一般所占比例很小,通常通过手工配置或者配备GPS接收器来获取自身的位置信息。

Horn公式

问题描述
Horn公式中最基本的对象是取值为true或false的布尔变量,变量的知识通过蕴涵式、纯否定两类子句来表达。给定某个由以上两类子句构成的集合,我们需要判断是否存在一个一致的解释,即一组使得所有子句都满足的变量(true/false)赋值,该解释成为该Horn公式的一个可满足赋值。

求解策略
从所有变量为false开始,依次将“只需且不得不”这样做以使得某个蕴涵式满足的变量置为true;一旦所有的蕴涵式都得到满足,再回头检查是否所有否定子句仍然满足。

这个确定移动方向的枚举:

  除此之外还有一种节点称为邻居节点(neighbor
node),邻居节点是指传感器节点通信半径内的其他节点。

集合覆盖

问题描述

必发娱乐官方网站 2

图中的点表示一组城镇,需要建设一些新的学校。

具体要求:

  1. 所有的学校都必须建在城镇上
  2. 从任意一个城镇触发,都应该可以在30英里的范围到达其中的某一所学校
    那么,最少需要建多少所学校呢?

较优解求解策略(贪心)
对每个城镇x,令S(x)为在其30英里范围内的城镇集合。
选取包含未被覆盖元素的最大集合Si,不断重复,直到所有元素都被覆盖。

贪心算法的逼近因子
贪心算法的解与实际的最优解的规模之比可能因问题输入的不同而不同,但是总小于ln(n)。我们称这一最大比值为贪心算法的逼近因子。

namespace DevExpress.XtraTreeList
{
    public enum DragInsertPosition
    {
        None = 0,
        AsChild = 1,
        Before = 2,
        After = 3
    }
}

  以下是几个常用术语:

写在最后
  • 立个Flag,TODO will be done some day。
  • 渣代码,且轻喷:worried:。

 

  • 到达时间(Time of
    Arrvial,TOA),信号从一个节点传播到另一个节点所需时间
  • 到达时间差(Time Diffrential of
    Arrival,TDOA),不同传播速度的信号从一个节点到达另一个基点所需要的时间之差
  • 到达角度(Angle of
    Arrival,AOA),节点接收到的信号相对于自身轴线的角度
  • 接收信号强度(Received Sinnal
    Strength,RSS),节点接收到无限信号强度的大小,也有称Received Sinnal
    Strength Indicator(RRSI),两个意思基本是一样的
  • 视距关系(Light of
    Sight,LOS),两个节点之间没有障碍物,能够直接通信
  • 非视距关系(Non Light of
    Sight,NLOS),两个节点之间有障碍物,不能直接通信
  • 跳数(Hop Count),两个节点之间的跳段之和
 

二.节点定位技术的基本思路

  节点定位的基本思路主要有两种:

  1.基于测距(Range-based):假设在传感器网络中某些节点位置信息已知,通过某些手段来估算其他节点的位置信息。在这里面通常有两个步骤:

  • 测距
  • 位置估算

  因为要通过信标节点得到未知节点的位置信息,必须先确定信标节点到未知节点的距离,才能得到未知节点的位置信息。举个例子说明一下:

  必发娱乐官方网站 3

  假如信标节点A位置已知为(x1,y1),节点M位置未知,要想求得M的位置,最简单的想法:假设B位置为(x,y),A到B的距离为d1,则有

  d12=(x-x12+(y-y12

  显然只根据一个方程这样是无法求得x和y的值,假若有两个信标节点呢?

  必发娱乐官方网站 4

  这样一来的话又多了一个方程:d22=(x-x22+(y-y22,此时可以解得方程组得到x和y,但是此时x和y是有两组解的,无法唯一确定x和y的值,因此需要考虑再假如一个信标节点:

必发娱乐官方网站 5

  这样一来的话就可以唯一确定x和y的值了,最基本的定位思想就是这样。这里举的例子是采用距离,还可以采用角度。

  一般情况最少需要知道未知节点和信标节点的三组距离或角度值,然后再通过位置估算方法确定位置。

  通常测距的方法有4种:

  1)基于到达时间(TOA)的测距

  这种方法是根据已知信号的传播速度及信号在发送节点和接收节点之间的传播时间来估算距离,这种方法要求能够非常精确地获取发送节点和接收节点之间的传播时延,这个是比较困难的,难度很大,不太适合无线传感器网络。

  2)基于到达时间差(TDOA)的测距

  这种方法中发送节点同时发送两种不同传播速度的信号、接收节点根据两种信号到达的时间差和他们的传播速度来计算距离。假若两种信号的传宝速度为v1和v2,到达时间分别为t1和t2,发送节点到接收节点的距离为d,则有:

  t1-t2=d/v1-d/v2

  可得d=(t1-t2)v1v2/(v2-v1)

  3)基于到达角度(AOA)的测距

  这种方法根据接收信号到达时候与自身轴线的角度来计算,这种方法对硬件成本要求很高,要求配备天线阵列,不太适合无线传感器网络

  4)基于接收信号强度(RSS)的测距

  信号在传播过程中会有衰减,无线信号的发射功率和接收功率存在某种映射关系,因此可以利用关系这个来估算距离,

 

  在获得了距离之后,就可以来估算位置了,常用的位置估算方法有下面两种:

  1)三边测量法

  上面举的例子中的位置估算方法就是三边测量法,此处不再赘述。

  至于某些文献上提到的三角测量法个人觉得跟三边测量法是一回事,就不再介绍了。

  3)最大似然估计法

  已知n个节点的坐标为(x1,y1),(x2,y2)……(xn,yn),它们到未知节点M的距离分别为d1,d2……dn,则有:

  (x-x12+(y-y12=d12

  (x-x22+(y-y22=d22

  ……

  (x-xn2+(y-yn2=dn2

  依次用第一个方程减去最后一个方程,可得:

  x12-xn2+y12-yn2+dn2-d12=2x(x1-xn)+2y(y1-yn)

  ……

  xn-12-xn2+yn-12+dn2-dn-12=2x(xn-1-xn)+2y(yn-1-yn)

  则可以表示成 AX = B

  其中A
必发娱乐官方网站 6B=必发娱乐官方网站 7X
=(x,y)T

  2.无需测距(range-free)

  无需测距的方法一般是利用网络连通性或者拓扑结构来估算距离,再利用三边测量法或者极大似然估计来估算位置。

三.常见算法

  1.基于测距(range-based)

  1)AHLos 算法 

  该算法是基于到达时间差的测距,信标节点首先向邻居节点以两种射频信号来广播消息,然后邻居节点根据到达时间差来估算距离,在接收到三个信标节点的消息之后,则根据三边测量法估算位置,邻居节点确定自己的位置之后转变为信标节点,也向邻近节点广播消息重复上述过程直至所有节点定位完成。

  2)RADAR算法

  该算法是基于RSS的测距,而基于RSS测距该算法有两种模型:经验模型和信号传播模型

  先说一下经验模型:

  必发娱乐官方网站 8

  在经验模型中,节点被分散在一定的区域内,并且保证所有的未知节点能够与信标节点直接通信,如图所示。然后事先在该区域内采集一些位置进行RSS强度测试,并以(x,y,RSS)的形式记录到数据库中。当进行定位时,未知节点同数据库中的数据进行比对,选择差值最小的三个或者三个以上点作为估算位置,然后再采用三边测量法或者下文的质心法来估算位置。

  信号传播模型:

  信号传播模型主要有两种模型:自由空间模型和shadowing模型

  自由空间模型假定信号发射功率和信号接收功率存在确定的映射关系: 

  必发娱乐官方网站 9

  其中PR是接收处的功率,PS是发射处的功率,d是发射点距接收点的距离,α是传播因子,视环境而定。

  shadowing模型:

  必发娱乐官方网站 10

  其中P(d)是未知节点处的信号强度或者信号发射功率,P(d0)是距信标节点或者基站d0处的信号发射功率(其中d0是参考距离,一般取1m),n是衰减因子,由于实际环境中存在噪声,所以引入了ß,比如在室内传播,会有墙壁或者门这些障碍物,就需要计算ß。

  2.无需测距(range-free)

  无需测距的定位算法不需要直接测量节点之间的距离或者角度,而是根据网络的连通性来实现位置估计得,典型的无需测距的算法主要有以下几种:

  1)质心算法

  质心算法基于两个假设条件:射频信号的传播遵循理想的圆球模型;节点的通信半径相同且不会改变。

  该算法利用了计算几何中质心的思想,假设n边形的顶点坐标分别为(x1,y1)……(xn,yn),设其质心坐标为(x,y),则有

  x=(x1+x2….+xn)/ n

  y=(y1+y2+….+yn)/ n

  算法核心思想为:信标节点周期性地广播包含自身位置信息的消息,在时间t内未知节点收到来自信标节点i的消息数目为Nr(i,t),而时间t内信标节点i发出的消息数目为Ns(i,t),那么未知节点和信标节点的连通指标为:

  C=Nr(i,t)/ Ns(i,t)

  如果C大于设定的阈值,则认为未知节点处于信标节点i的覆盖区域内,即与信标节点i连通。这样对于每个未知节点都可以选出与其连通的所有信标节点,然后把这些信标节点的质心作为该未知节点的坐标。

  质心算法是一种完全基于网络连通性的定位算法,其计算和实施难度都比较小,但是算法精度不高,并且通常要求信标节点具有较高的密度。

  2)DV-HOP(Distance Vector-Hop)算法

  DV-HOP算法是为了避免对节点距离直接测量而提出的一种基于矢量路由的非测距定位算法。该算法的核心思想是通过距离矢量路由方法获取未知节点与信标节点之间的最小跳数,并计算每跳的平均距离,然后以每跳的平均距离与最小跳数的乘积作为未知节点与信标节点的估算距离,再使用三边测量法估算未知节点的坐标位置。举个例子:

  必发娱乐官方网站 11

  A、B、C为信标节点,M为未知节点,A到B和C的距离分别为40m和100m,而A到B和C的最小跳数分别为2和5,则A的平均跳距为:

  (40+100)/
(2+5)=20m,同理可以得到B和C的平均跳数为24m和22.5m,则可以计算M距离三个信标节点的距离分别为:

  3*20m,2*24m,3*22.5m,然后就可以利用三边测量法估算出M的坐标。这种方法实现比较简单,但是精度较差,不适合稀疏的以及拓扑不规则的网络。

  3)APIT算法

  APIT算法的基本思想同质心算法的思想类似,它利用由信标节点组成的三角形覆盖重叠区域来确定未知节点的位置。在APIT算法中,未知节点首先在其邻居节点中收集信标节点的信息。然后任意选取3个信标节点,判断自己是否在这3个信标节点组成的三角形区域内,然后不断这样循环选取3个信标节点进行判断,这样,未知节点可以确定多个包含自己的三角形区域,这些三角形区域的重叠部分是一个多边形,它确定了更小的包含未知节点的区域,然后以这个多边形区域的质心作为未知节点的坐标。

  4)MAP算法

  MAP(Mobile Anchor
Point)是一种基于移动信标节点的非测距定位算法,也有称为MAN(Mobile
Anchor
Node)。其基本思想是利用可移动的信标节点在监测区域中移动并周期性的广播其当前的位置信息,然后可以确定两条以未知节点为圆心的弦,这两条弦的垂直平分线的交点就是圆心。

  必发娱乐官方网站 12

  如图所示,S为未知节点,M为移动的信标节点,在T1时刻M移动到S的通信范围之内,然后在T5时刻移出S的通信范围,这样就可以确定了两条弦
 T1T5,在T12时刻M又重新移动到S的通信范围之内,然后又在T15时刻移出S的通信范围,这样又可以确定一条弦T12T15,这两条弦的垂直平分线的交点即为圆心S的坐标,然后以圆心坐标作为未知节点S的位置。

  该算法有与其他非测距定位算法相比有较高的精确度,但是缺点是移动节点是必须要有足够能量支持其在监测区域内移动,并且当未知节点的位置发生变化时,该算法有比较大的误差。

  5)Amorphous算法

  Amorphous算法与DV-HOP算法类似,其分为三个阶段:

  第一阶段:计算未知节点与每个信标节点之间的最小跳数

  第二阶段:假设网络中的节点通信半径相同,并且每跳的平均距离等于节点的通信半径,计算未知节点到每个信标节点的距离

  第三阶段:采用三边测量法或者最大似然估计法估算未知节点的位置

  6)凸规划定位算法

  凸规划定位算法的核心思想是:如果两个节点能够直接进行通信,则它们之间的距离必定小于节点的通信半径。

  必发娱乐官方网站 13

  如图所示,黑色实心点为信标节点,白色空心点为未知节点,假若未知节点能与信标节点通信,则其必在以信标节点为圆心、通信半径为半径的圆内,这样的话,多个这样的圆的相交区域必然包含了未知节点,然后以相交区域构成的矩形的质心作为未知节点的坐标。

  7)Ring-Overlapping算法

  必发娱乐官方网站 14

  该算法利用交叠环的思想进行定位,比如S为未知节点,A、B、C为信标节点,若A发出射频信号,而S处的信号强度RSS小于B处的信号强度而大于C处的信号强度,则S必在以A-B为内半径、A-C为外半径的环形区域内,类似地分别可以得到以B、C为中心的环形区域,而S必在这些环形区域的交叠区域内,然后以交叠区域的质心作为S的坐标。

   以上算法都是有信标节点的定位算法,曾有人提出了一些没有信标节点的定位算法如SPA(Self-positioning
Algorithm)算法,这种算法主要是建立全局坐标系来估算未知节点的位置,但是这种算法复杂度非常高,不适合用于大规模网络,也有人提出针对SPA算法的改进算法,如SDGPSN(Scalable
and Distributed GPS free Positioning for Sensor Networks)算法。

  还有一部分人提出了一些其他的算法,比如AFL(Anchor-Free Distributed
Localization in Sensor
Networks)算法,其利用的是局部估算方法。还有人提出了基于分簇的定位算法(Using
Clustering Information for Sensor Network Localization)。

  定位算法暂时就介绍这么多了,相关深入内容将在后面继续讲解。

相关文章