【Ad Hoc】叁 OLSR 协议详解

1、LSR 协议

LSR 为基于链路状态的路由算法。如何判断链路状态呢?在无线通信的环境下,只需要节点能够收到另一节点的包,就说明链路有效。另一方面,为了建立端到端的路径,路由算法需要发现并检查一跳由多个单跳链接组成的多条链路的可用性,这就需要不断的洪泛广播(flooding)来进行。这种洪泛的方式是非常浪费的。

LSR 示意图

为了在网络中同步节点状态,需要各个节点进行洪泛广播,产生大量冗余的通信,在能源受限的移动网络中是非常不经济的。OLSR 通过有选择的洪泛转发(MPR: Multi-Point Relay)来解决这个问题。

2、OLSR 协议

OLSR(Optimized Link State Routing: RFC 3626, October 2003)是一种基于连接状态的表驱动无线路由协议,它在 Ad Hoc 路由协议中的位置如下图所示。

Read More

【Ad Hoc】壹 速览 Ad Hoc 网络

一、概述

自组织网络(Ad Hoc)是一种移动通信和计算机网络相结合的网络,是移动计算机网络的一种,用户终端可以在网络内随意移动而保持通信。

早在上世纪,随着 IEEE 802.11标准的开发,Ad Hoc 的概念就已经诞生了,IETF 标准化的 Ad Hoc 网络称为 MANET,现在通常用 MANET 描述一切 Ad Hoc 网络。在随后的几十年中,Ad Hoc 相关技术稳步发展,在军事、民用、商业等许多重要领域都具有独特优势。

在5G 和人工智能浪潮迭起的今天,车联网、无人机网络等新兴技术的兴起,Ad Hoc 网络又焕发了新的生命力。

Ad Hoc 网络采用分组交换机制,网络中的每个用户终端都建有路由器和主机两种功能。作为主机,终端可以运行各种面向用户的应用程序;作为路由器,终端需要运行相应的路由协议。

传统无线网络与 ad-hoc 网络

Read More

【Ad Hoc】贰 AODV 协议详解

一、AODV 概念

AODV 是按需路由协议,当一个节点需要给网络中的其他节点传送信息时,如果没有到达目标节点的路由,则必须先以多播的形式发出 RREQ 报文,邻居节点收到 RREQ,首先判断目标节点是否是自己,如果是,则向发起节点发送 RREP,如果不是,首先在路由表中查找是否有到达目标节点的路由,如果有,则向源节点单播 RREP,否则继续转发 RREQ 进行查找。

在网络资源充分的情况下,AODV 协议可以通过定期广播 HELLO 报文来维护路由,一旦发现某一个链路断开,节点就发送 ERROR 报文通知那些因为链路断开而不可到达的节点,删除相应的记录或者对已经存在的路由修复。

AODV 特点如下:

  • 节点只存储需要的路由

Read More

【蓝桥杯】第一讲 递归与递推

递归和递推实则是两个互逆的过程。

递归从问题本身出发,寻找问题相似的部分,利用分而治之或简而治之的思想,将庞大的问题划分为小问题,再通过边界条件的限定,得出答案。代码一般比较简洁,但阅读起来确实思维的逆向过程,可能会不容易理解,且遇到输入规模很大的问题,容易因为函数的多次调用导致堆栈溢出。

递推从简单的实例出发,发掘小问题之间的规律,再扩展延伸满足整个问题的条件,进而求解。代码符合人的正向思考过程,易于理解,不过循环嵌套显得冗余,相同问题代码量一般要比递归的解法多。

下面通过一些例子一步一步地讲述两种思想的思考过程。

1、指数型枚举

题目链接

Read More

3.语法分析 Part1

一、语法分析的任务

我们已经通过词法分析的学习掌握了从将源程序转化为记号流的过程。

对于之后的语法分析器阶段,我们在编译器设计的早期,只实现了分析源程序是否合法,如果不合法就返回程序的出错信息给程序员,退出源程序的编译过程。程序员对代码进行修改后就重启该编译过程,重新进行词法分析和语法分析。

后期的编译器设计过程中,我们的语法分析过程就通常需要生成一个抽象语法树的中间表示。该语法书输出到后续阶段,用于语义分析器或者代码生成器进行进一步的处理。这样的新设计使语法分析器能够更加专注于自己的任务,将语义检测和代码生成的任务交给后续阶段再来进行处理。

语法分析器是前端比较核心的模块,负责处理程序员输入的程序,产生编译器后端需要使用的第一个非常核心的数据结构——抽象语法树

单独提出语法分析器的模块如下,输入是记号流,输出是语法树

Read More

4.语法分析 Part2

在详细地介绍语法分析的两个任务及其具体内容后,我们来讨论判断语法正误的实现算法。

一、自顶向下分析

1.1 基本思路

上文已经明确了语法分析的定义,即看一个文法 G 是否存在对句子 s 的推导。自顶向下分析就是其中一个比较典型的算法,其基本逻辑是:

  • 通过文法 G 随意推导出一个句子 t ,然后拿 t 和目标句子 s 进行对比
  • 如果 t == s ,则成功
Read More