答辩陈述在线视频

顾钊铨博士的博士论文答辩会现在开始

请杨广文教授来主持

好 大家下午好

按照我们清华大学博士学位论文答辩的程序

首先由我代表学风委员会

来宣读一下顾钊铨同学答辩委员会名单

主席 我 杨广文

由我来负责

我是清华大学计算机系的

然后崔丽老师是中科院计算所的

牛建伟老师是北京航空航天大学的

黄隆波老师是清华大学交叉信息研究院的

还有华强胜老师是华中科技大学计算机学院的

那么秘书由王永才老师（担任）

他是交叉信息研究院的

那么 下面我们先宣布一下答辩的纪律

第一 答辩委员会成员

在答辩过程中不得进行与本次答辩无关的活动

不得随意出入

第二 在场所有人员在答辩过程中保持肃静

手机 电子设备应关闭或静音

好 那么我们下面答辩会议正式开始

首先我们请王永才把顾钊铨同学的

一些情况和一些学习成绩情况做一个简单的汇报

顾钊铨同学他在2007年到2011年

在清华大学交叉信息研究院攻读学士学位

2011年到2015年在清华大学交叉信息研究院

攻读博士学位

他的博士生课程及成绩情况如下

中国马克思主义与当代 90分

资格考试 90分

组合数学 97分

计算几何 93分

高等理论计算机科学上 99分

高等理论计算机科学下 94分

算法理论导论 95分

自然辩证法概论 90分

网络系统的建模与分析 89分

算法与算法复杂性理论 93分

算法分析与设计 96分

他的学位论文题目是

认知无线电网络中分布式信道汇聚算法研究

他发表文章情况

发表文章11篇

其中包括INFOCOM 2015 两篇

INFOCOM 2013 包括SECON、SIROCCO等

网络领域的一些比较好的会议文章

这就是顾钊铨同学的一些基本情况

好 那么现在分学位委员会同意顾钊铨同学答辩

那么按照程序 下面就是做答辩报告

报告在30到45分钟 现在开始

Thanks for the introduction.

Hello everyone!

Thank you for attending my thesis defense.

I'm Zhaoquan Gu and my supervisor is Qiang-Sheng Hua.

The title of my thesis is

Distributed Rendezvous Algorithms for Cognitive Radio Networks.

First of all, I will introduce the background and the motivation.

Then, I will go to the main parts of my thesis.

The first part studies blind rendezvous for Cognitive Radio Networks.

The second part studies oblivious blind rendezvous problem for Cognitive Radio Networks.

The third part studies blind rendezvous for Heterogeneous Cognitive Radio Networks.

Then, I will conclude the thesis and list some future works.

In my thesis,

I study the blind rendezvous problem for Cognitive Radio Networks,

and I will introduce what's rendezvous.

Actually, rendezvous happens around us every day.

For example, two people go for a date and they have to meet at some place,

and we call this process rendezvous.

Look at the following picture,

two people get lost in a shopping center

and one of them lost his mobile phone unfortunately.

Then how can they meet together?

One of them may search the other places and one of them may wait at this fixed place,

and we call it rendezvous if they finally find each other.

Here is another example.

Suppose some robots are dispatched to the moon to carry out some tasks.

Once they land there, they don't know the other robots'positions.

Rendezvous problem is how can these robots get together at the same place as quickly as possible.

In my thesis,

I study the rendezvous problem for Cognitive Radio Networks, and I will introduce the background.

Nowadays, there are more and more wireless devices,

and the increasing demand for wireless service makes the unlicensed spectrum overcrowded.

However, the utilization of the licensed spectrum is pretty low.

Therefore, the unlicensed users are allowed to access the licensed spectrum

with no interference to the licensed users, that is primary users.

Technically speaking,

the licensed spectrum is divided into N channels with labels from 1 to N.

And there are two types of users coexist in the network, primary user and secondary user.

We say a channel is available for the secondary user

if it's not occupied by any nearby primary users,

such as 1, 4, N are available for the secondary user,

and then the secondary user can access the available channels.

In the following parts, I will use “user” to be the secondary user.

Here is an example.

There are four primary users in the network and each of them uses some channels,

and the cycle means the interference range

and any secondary user in the range cannot use the channel that occupied by the primary user.

For example, user A cannot use channel 3,4 or channel 6,

so the available channel for user A is 1,2,5.

Similarly, the available channel for user B is 3,4,5.

If the users want to communicate with each other,

they should find a common channel to establish a communication link,

that is they should find channel 5 and we call this process rendezvous.

The first part of my thesis studies the blind rendezvous problem for Cognitive Radio Networks.

And I will introduce the preliminaries,

and we present both Global Sequence and Local Sequence based rendezvous algorithms.

In this talk, I will show these three points.

To begin with, I will introduce what's blind rendezvous.

Suppose two users can find a set of available channels,

if they want to communicate with each other,

they should find a common channel,

some works assume a central unit or a central controller exists to simplify the process.

However, the central unit can be easily congested or jammed by an attacker.

So we prefer distributed algorithms such that the users do not know the other's information.

So the users have to access the channels in such a blind way.

We define the blind rendezvous problem for two users is

to access the same available channel at the same time, without the other user's information.

Here is the system model.

There are N channels from 1 to N.

And a channel is available for the user is it's not occupied by any nearby primary users.

For example, there are three available channels.

Time is divided into slots of equal length,

and each user can access an available channel in each time slot.

We say rendezvous is achieved

when the users access the same channel in the same time slot.

Time to rendezvous represents the number of time slots cost before rendezvous.

Here I'll show an example.

For example, user A has three available channels 1,2,5,

and user B has 3,4,5.

If they want to communicate with each other,

they can use a simple idea: round robin,

that is user A accesses channels by repeating its available channels 1,2,5,

and user B accesses channels 3,4,5.

If they start at the same time, rendezvous happens on channel 5.

However, if user A is one time slot earlier, rendezvous never happens.

We call the first situation synchronous and the other one asynchronous.

Our goal is to design distributed algorithms for asynchronous users to achieve rendezvous in the network.

This blind rendezvous problem has the following challenges.

First, the users cannot know the information of the others,

such as the others' available channels, or the others' start time.

Second, the users can start the rendezvous problem at any time,

and the maximum time to rendezvous should be bounded.

Third, we should design efficient algorithms for both symmetric and asymmetric users,

here symmetric users mean the users have the same set of available channels.

In my thesis, I first propose global sequence based algorithms

and the intuitive idea is to construct a sequence of fixed length,

and then each user accesses the channels by repeating the sequence.

Here are some related results.

From the table, we see that our result works best.

In my thesis, I show that this result can be improved to O(1) for two symmetric users,

and we also show the lower bound is Omega(N^2).

From this table, we know that our algorithm is nearly optimal

and I will show the DRDS based algorithm.

The global sequence based algorithm is to construct a global sequence

and each user can access the channels by repeating the sequence.

If some channel in the sequence is unavailable, we can choose another available channel.

We define a good global sequence satisfying the two conditions.

First, the sequence has bounded length.

Second, two users using the two global sequences can rendezvous at every channel asynchronously in T time slots.

For example, this is a good global sequence.

If two users start at the same time,

they can rendezvous on channel 1 and 2.

If one user is one or two time slots later than the other,

they can also achieve rendezvous on channel 1 and 2.

There are the other three situations.

Obviously, if two uses access the channels by repeating such good global sequence,

once there exists some common available channel, rendezvous happens.

However, how to construct such good global sequence?

In our work, we introduce an efficient tool called Disjoint Relaxed Difference Set.

A set is called Relaxed Difference Set if for every value d,

there exists at least one ordered pair satisfying the equation,

for example, under Z6, (1,2,4) is a RDS.

And we define a set to be Disjoint Relaxed Difference Set

if any element Di is a RDS and any two elements do not intersect.

For example, (1,2,4), (0,3,5) is a DRDS.

In our work, we show that any good global sequence corresponds to an DRDS.

For example, this is the good global sequence and this is the DRDS.

Notice that, the position of channel 1 is 0,3,5,

and they correspond to the RDS (0,3,5),

and the positions of channel 2 is 1,2,4, and they correspond to the RDS (1,2,4).

In our work, we construct P RDS to compose an DRDS under Zn,

here n equals to 3P^2, and I will show the construction.

When n equals 3P^2, we first divide it into P frames,

and each frame contains 3P numbers.

Then each frame is divided into 3 segments.

Then we construct each RDS.

For the i-th set, we choose two numbers from S_01, S_02 to be here,

and we choose two numbers from these two sets.

For the i-th set, S_i0, we choose all numbers in the set and continue this process.

The numbers are chosen according to the equation

and in our work we show that D_i is an RDS.

Since we construct P RDS, they compose the DRDS.

I will give an example.

For example, n equals 27,

we divide it into three frames and each frame contains 9 numbers.

Then each frame is divided into 3 segments, and each segment contains 3 numbers.

For the first set, the three numbers 0,1,2 are put to the set,

and then choose two numbers 3,6, and two numbers 13 and 16, then 22 and 25.

We can check that D0 is a RDS.

Similarly, we can construct D1 and D2.

We can check that they compose the DRDS.

After the construction,

we can design the rendezvous algorithm for the rendezvous problem.

First, there are N channels,

then we can find the smallest prime number P larger than N,

then we construct the DRDS under Z_3P^2,

then we reconstruct the good global sequence.

Two users access channels by the good global sequence can achieve rendezvous in 3P^2 time slots.

We also add a listening stage to guarantee rendezvous for symmetric users in a shorter time.

We also show that the lower bound of such good global sequence is Omega(N^2)

and our algorithm is nearly optimal.

Notice that, the rendezvous algorithms for two users

can be extended smoothly to the multiple users in a multihop network,

and in the following parts, I will focus on the rendezvous algorithms for two users.

Moreover, we present Local Sequence based algorithms for the problem,

the intuitive idea is to design different sequences based on the user's identifier

and the set of available channels.

Different from the global sequence based algorithms,

we assume each user has ID

and we can construct different sequences based on this information.

Here are some related works, and our result works well under most situations,

and we can improve them to O(1) for two symmetric users.

Here is a simple example.

Two users have three available channels.

Assume each user has a distinct ID,

and we can construct different sequences based on the ID and the set of available channels.

For example, if the user A, ID is 1,

we can construct the sequence 111111,222222;

and for anther user, suppose the ID is 2,

we can construct the sequence 3,4,5,3,4,5.

Then rendezvous can be guaranteed.

In this part, we introduce an efficient tool called Disjoint Relaxed Difference Set,

then we show the equivalence of an DRDS and a good global sequence.

Then we present the DRDS based rendezvous algorithm for both symmetric and asymmetric users.

We also propose Local Sequence based rendezvous algorithms based on the user's local information.

The second part of my thesis studies the oblivious blind rendezvous problem for Cognitive Radio Networks,

which is firstly proposed in our works.

First, I will introduce the preliminaries.

Then we will propose the rendezvous algorithms for anonymous users.

Then we will introduce the rendezvous algorithms for non-anonymous users.

More importantly, we will introduce the first fully distributed algorithm for the problem.

First of all, I introduce the motivation of proposing this problem.

Almost all blind rendezvous algorithms assume the licensed channels have fixed labels,

but in practice the same frequency band may be labelled differently by different administrations or different entities.

Second, the blind rendezvous algorithms assume each user has full knowledge of the network,

such as the labels, the number of channels, or even the network size.

However, it's hard to obtain in practice.

So we propose the oblivious blind rendezvous problem that the user cannot know the labels of the channels,

and we are to design fully distributed algorithms only based on the user's local information.

Here is the system model.

There are N channels and ui represents certain frequency band.

A channel is available if it's not occupied by any nearby primary users.

For example, the three channels are available.

However, the users do not know the label of the sensed available channels,

and they have to label these channels locally.

For example, this user can sense three available channels,

but she doesn't know the labels,

so she has to local label it as 1,2,3.

For another user, suppose he can sense four available channels,

but he doesn't know the labels and he has to local label it as 1,2,3,4.

Notice that, even the same channel u1 can be labelled differently by the users.

Time is also divided into slots of equal length,

and the user can access an available channel in each time slots.

We study anonymous users and non-anonymous users in the thesis,

here anonymous users mean they are indistinguishable from each other.

We also study the synchronous users and asynchronous users.

Here is an example.

Suppose user A has two available channels and she local labels it as 1 and 2,

and user B has four available channels.

If they want to communicate with each other,

they should find the common available channel u1.

For example, user A can access the channels by repeating the sequence 1122,1122,

and the corresponding channels u1 u1 u3 u3.

The second user can access channels by the sequence 1234,1234,

and the corresponding channels are like this.

Under this situation, two users can achieve rendezvous on channel u1.

However, if the second user is four time slots later, then they can never rendezvous.

Then oblivious (blind) rendezvous problem has the following challenges.

First, the users do not know the label of the channels,

and even the same channel could be labelled differently by the users.

Second, the users can start the rendezvous process at any time,

and we should bound the maximum time to rendezvous.

Third, we are to design the fully distributed algorithms

and the users do not know the network information,

such as the number of channels, network size.

In the first place, we propose algorithms for anonymous users.

For two anonymous users,

we present an impossibility result such that no deterministic algorithm exists.

Suppose there exists some deterministic algorithm,

suppose user A has N/2+1 available channels,

then through the algorithm, she can get an output in each time slot.

Similarly, if another user also has N/2+1 available channels,

and through the function, he will get the same output in each time slot.

However, if the local label ai, bi does not represent the same channel,

rendezvous never happens.

The user A can label the channels like this and user B can label the channels like this,

though there exists some common available channel, rendezvous never happens.

This is because F is deterministic and the inputs of the two users are the same,

and they will get the same output in any time slot.

However, it's just local label, but the local labels do not represent the same channel.

Since there exists no deterministic algorithm for this situation,

we propose randomized algorithm for a special case that all channels are available.

A simple idea is random selection,

that is each user accesses channels randomly in each time slot.

Obviously the expected time is N time slots.

Though the random selection seems to be a good solution,

we are to find out if there exist some better algorithms.

Actually the answer is YES and in our work we design this algorithm,

it's called stay or random selection.

With probability p, the user keeps accessing one channel for N time slots,

and with probability 1-p,

the user accesses the channels according to a random permutation of N channels in N time slots.

If rendezvous doesn't happen, we just repeat the process.

Notice that, our algorithm works for both synchronous and asynchronous users.

And I will introduce the analysis for synchronous users.

We suppose N is large enough, and denote the expected time as T.

User A has N available channels and user B has N available channels.

Since they have two choices to make, they can throw some coins to decide which choice to take.

For example, if they choose the first choice,

(user A) will access a fixed channel for N time slots,

and user B also will access a fixed channel for N time slots.

The probability of this situation is p^2 and the expected time is N+T, since N is large enough.

The other situation: if A accesses a channel in N time slots

but user B accesses the channels by repeating a random permutation.

The probability of this situation is 2p(1-p) since user A can do this (same) thing.

And the expected time is N/2.

Actually, it should be (N+1)/2, but N is large enough, we omit the plus one.

The third situation is user A accesses the channels by a random permutation

while user B accesses the channels by another random permutation.

And the probability of this situation is (1-p)^2 and this is the expected time.

Since it's complicated, I omit the details.

Through the recursion equation,

we can compute the expression of T and by finding appropriate p values, we can minimize the T.

In our work, we list the results such that when p is this,

we can get the expected time to rendezvous.

But for asynchronous users, this is very complicated and we omit the details.

But when p equals 0.200, we can get expected time as 0.9111.

Through the comparison,

we know that our algorithm is better than random selection,

which is a more or less surprising result.

For non-anonymous users, we first present a lower bound,

and then we design deterministic algorithms for both synchronous users and asynchronous users.

This algorithm is the fully distributed algorithm and I will introduce it in details.

In order to design fully distributed algorithm,

the user only knows the ID and the number of available channels.

And there are some limitations:

such as the user doesn't know the global information such as the number of channels,

the maximum ID, or the other users' information.

For example,

user A has three available channels and user B has five available channels,

if they want to communicate with each other,

they should find the common channel u1.

However, user A only knows her ID is 2 and she has three available channels,

user B only knows his ID is 5 and he has five available channels.

But how to design the rendezvous algorithm such that they can rendezvous in any case.

This seems to be an impossible task.

In our work, we design rendezvous algorithms just based on the two information.

And I will show the construction.

First, we convert the user's ID.

In the first place,

we find the smallest prime number p that is no less than the number of available channels.

Then we convert the user's ID under base p-1,

and we denote the output as this.

Then we construct the vector.

Here the first element is 0, this is very special, and the other elements (are) just plus one.

For two users, since user A: ID is 2 and there are three available channels,

the corresponding prime number is 3

and we should convert the ID 2 under base 3-1, under base 2,

so it is (1,0), then the vector is (0,2 is 1 plus 1, and this is 1).

For the second user, the prime number is 5

and we should convert the ID under base 4,

we should convert the ID 5 under base 4 and it's (1,1),

and the vector is (0,2,2).

After the conversion based on the user's ID, we construct the sequence as follows.

The sequence consists of p frames and each frame contains |D| segments.

For example, for the first user,

the prime number is 3, and the vector is (0,2,1).

The first frame contains three segments,

and the first segment contains six numbers.

Since the first element of the vector is 0,

we construct the sequence as 1,1,1,1 plus 0, 1 plus 0, 1,1,1, for six time slots.

For the second segment, this bit is 2 and the first number is 1,

and the second number is 1+2=3, and then 3+2 under modulo 3 is 2, so 1,3,2,1,3,2,

and the third segment is 1,2,3,1,2,3 because this element is 1 and we (let) 1+1, 2+1.

Then we can construct the second frame,

the first number is 2 and there are six 2,

and this is 2,1,3 because 2+2, 1+2,

and this is 2,1,3.

And the final segment is 2,3,1,2,3,1.

Similarly we can construct the third frame of the sequence.

After the construction, the users can access the channels by repeating the sequence.

For example, this is the sequence based on the local label

and this is the channels corresponding to the local labels.

And consider another user B, this is his sequence and this is the channels.

Then rendezvous can be achieved on channel u1.

In our work, we show that,

two asynchronous, non-anonymous users can achieve rendezvous a short time,

but we omit the details of the proof.

In this part, we study the oblivious blind rendezvous problem for anonymous users and non-anonymous users.

For anonymous users,

we present an impossibility result and we propose an efficient randomized algorithm.

For non-anonymous users,

we propose deterministic algorithms for both synchronous and asynchronous users.

Finally, we present the first fully distributed algorithm which only utilizes the user's local information.

The third part of my thesis studies the blind rendezvous for Heterogeneous Cognitive Radio Networks,

this is a special type of Cognitive Radio Network and I will introduce this part briefly.

I will introduce these two points.

This is the system model.

Similar to the blind rendezvous problem, there are N channels and all users know the labels.

Each user can only sense a set of continuous channels.

For example, there are N channel and user A can only sense continuous channels 2,3,4,

and anther user can only sense continuous channels 3,4,5,…

After spectrum sensing stage, each user can find a set of available channels,

and time is also divided into slots of equal length,

and we use Maximum Time to Rendezvous to evaluate the rendezvous algorithms.

This problem has the following challenges.

First, different users may have different capabilities to sense the licensed spectrum.

Second, the users can start at any time.

Third, we are to reduce the maximum time to rendezvous,

since traditional rendezvous algorithms for Cognitive Radio Networks has the maximum time as O(N^2),

however when the user can only sense a small fraction of the licensed spectrum, the value is too large.

In our work, we first present algorithm for fully available users,

that is all channels in the user's sensing capability set are available,

and I will just introduce the intuitive ideas.

Suppose each user can access two channels in each time slot,

then we introduce two pointers,

the fixed pointer fp accesses the first channel of the user's capability set,

while the moving pointer mp traverses the channels like this.

User A has five available channels and user B can sense six channels.

The moving pointer can traverse the channels, like this,

and when the moving pointer of user B moves to the position of user A's first channel,

rendezvous happens.

In our work, we show that rendezvous can be guaranteed in a short time.

For partially available users that not all channels in the user's capability set are available，

we also present the algorithm.

The intuitive idea is also to access two channels in each time slot,

and we also use two pointers.

The fixed pointer accesses one fixed channel just for a long time,

the moving pointer can traverse the channels,

once the moving pointer has already traversed the available channels, we move the fp pointer,

this is different from the first situation.

After the modification, here is an example for two users.

The moving pointer can traverse the available channels,

and when the moving pointer has already traversed the available channels,

we move the fp pointer,

and then rendezvous can be guaranteed.

In our work, we show that rendezvous can be guaranteed in this time slot,

but we omit the details.

However, in practice, each user can only access one channel in each time slot,

and here we suppose each user can access two channels in each time slot.

Therefore, we should design the rendezvous scheme for the users

such that they have only two available channels.

And in our work, we design a sequence of length O(loglog N),

and we prove that for two sets which have only two available channels,

rendezvous can be guaranteed in O(loglog N) time slots.

Then for the Heterogeneous Cognitive Radio Networks,

we just need to add the loglog N factor to the time complexity.

And this is the result comparison.

From this table we know that,

our algorithm works better than these two algorithms,

since this is almost linear and this is just (based on) the number of available channels,

but this is the capability set.

Finally, I'd like to conclude the thesis and list some future works.

In the first part,

we study the blind rendezvous problem for Cognitive Radio Networks

and we present both Global Sequence and Local Sequence based algorithms.

And this is the DRDS algorithm,

and we improve the DRDS based algorithm such that two users can achieve rendezvous in O(1) time slots,

and we also show the lower bound as Omega(N^2), such that our algorithm is nearly optimal.

In the second part,

we study the oblivious blind rendezvous problem for Cognitive Radio Networks.

We propose randomized algorithms for anonymous users

and deterministic algorithms for non-anonymous users.

We also propose the first fully distributed algorithm.

And this is the lower bound,

this is the fully distributed algorithm,

compared to the lower bound, our algorithm is pretty good.

In the third part,

we study the blind rendezvous for Heterogeneous Cognitive Radio Networks.

And this is the related result.

Actually, rendezvous can be applied in many areas and there are many important future works.

From the theoretical view,

we are to derive tighter lower bound

and to design better or even optimal algorithms for the two situations.

When rendezvous can be applied in many other fields,

such as rendezvous search game,

rendezvous with jamming,

and rendezvous in robot control,

there are many interesting works to do.

From the practice view,

when the licensed channels have different bandwidths,

we are to design good rendezvous algorithms for this situation.

And in practice,

when the user's available channels may vary due to the primary users' usage,

we are to design self-adapting algorithms.

More importantly, in a multihop cognitive radio network,

the topology may vary when the users join or leave,

and not all users may share some common available channels,

we are to design scalable and flexible rendezvous algorithms.

And this is my publication for the rendezvous problem in Cognitive Radio Networks.

And during my PhD studies,

I have done some other works,

such as scheduling in Wireless Sensor Networks,

and controllability of Dynamic Networks.

Here are some related publications.

This is the reference.

Finally, there are so many people to thank.

I will thank my supervisor Qiang-Sheng Hua for his supporting in my studies and research,

thank the thesis defense committee and the secretary,

and thank the teachers and the students in IIIS,

and thank all of you for your coming and listening.

Thank you!