Přepis řeči - A KNAPSACK PROBLEM FORMULATION FOR RELAY SELECTION IN SECURE COOPERATIVE WIRELESS COMMUNICATION

0:00:13	and
0:00:14	and i'm the last one i'll try to make it a fish and
0:00:18	a is but yeah yeah that time and now we can spend a whole leaving here no i don't think
0:00:23	um
0:00:25	this article of a
0:00:26	this paper or uh is a knapsack problem uh formulation for really selection in secure corporate people that wireless was
0:00:33	communication
0:00:34	i i this work yeah yeah um is a collaboration with a one Q will uh
0:00:39	a professor for trouble profess of a and myself
0:00:43	and will start by a short introduction talking about the uh um
0:00:48	uh a cooperative jamming uh the system will introduce the system the model that we are considering for this
0:00:54	um and then we will uh formulate their uh an set
0:00:58	uh
0:00:59	problem uh for the selection of um minimal set
0:01:03	of really is uh to cooperate um
0:01:06	a a in the jamming
0:01:08	uh as uh this result that you know uh optimization problem that requires exponential complexity we will um
0:01:15	all uh all four three uh alternative a solution that um
0:01:20	oh four as um significant the
0:01:22	saving in complexity
0:01:24	and we will introduce a it would show some assimilation analysis of but these algorithms
0:01:29	and finally some concluding remarks
0:01:33	a so we know
0:01:35	a a cooperative the wireless communication system
0:01:37	the additional uh um
0:01:39	and degrees of freedom that are offered by those cooperating uh really is uh maybe use them to degrade great
0:01:45	uh channel
0:01:47	to uh potentially drop or
0:01:49	uh and they are uh
0:01:52	they can use the uh uh jointly
0:01:54	some way a
0:01:56	B to send a a collaborative them
0:01:59	a jamming signal
0:02:00	uh
0:02:01	to that you've drop
0:02:03	uh this type of uh a scheme was uh considered uh a would for protection meaning that if we have
0:02:09	a a an available really we use all in available relays
0:02:14	a for the purpose of jamming
0:02:16	uh and they a send a way uh version of the same jamming signal uh
0:02:23	for the two D pro
0:02:25	and this work was been done in two thousand nine by
0:02:28	don't hand problem
0:02:30	uh since no
0:02:32	it has been shown that
0:02:33	at some point
0:02:34	and as the that lot number of uh
0:02:38	grows
0:02:39	at some point
0:02:40	the that we get a introducing the relay for the jamming
0:02:44	is is small
0:02:47	uh and this has been a shown by um
0:02:50	one and uh
0:02:52	swindle to her in two thousand nine
0:02:54	uh considering that that and the fact that
0:02:57	the larger the system is
0:02:59	the larger uh the communication that a it is and uh
0:03:03	the synchronization requirement
0:03:05	that bring just to to the full question uh when you have a and collaborating really is and we previously
0:03:11	used all of them
0:03:12	uh can now the sec you rate requirement be a cheap tool close to to the maximum be achieved
0:03:17	we do a smaller or you're
0:03:20	uh uh uh activity
0:03:23	and the objective that
0:03:24	we we put forth and this is to identify i mean a more set of of uh relays
0:03:30	such that the predetermined secrecy receive rate the objective is a G
0:03:35	uh
0:03:36	first let's in the system that are considering
0:03:39	assuming we have a a a a a source transmitting a signal to the destination and
0:03:45	that you drop or is hearing the same message
0:03:48	oh we know the channel a between this uh a source and the destination by a just zero and between
0:03:54	the source and the proper or by G zero
0:03:57	also seem we have and
0:03:59	uh cooperating relays
0:04:01	and i and for each one of the really a uh with assume we have
0:04:05	we know the channel uh from
0:04:07	for example a really really high
0:04:09	to the destination marked by a giant again from the really
0:04:13	uh to that you drop or might but by G I and you seem we know we have knowledge of
0:04:17	the channel and bob
0:04:20	uh we assume um white gaussian noise of be zero mean and variance sigma squared
0:04:25	assume the energy for the
0:04:28	transmitted symbol X is uh one
0:04:31	and at the sort transmission power for the
0:04:34	the
0:04:35	so the symbol is P
0:04:37	uh all S
0:04:39	uh the really transmit meet a common jamming signal uh Z and we assume that each one transmit a weighted
0:04:46	version of signal
0:04:50	a for this uh scenario we basically have here
0:04:53	for the the signal received at the destination
0:04:57	is composed of the first element that is the message that was sending
0:05:01	uh in the second part is uh the version of the jamming signal that we have transmitted
0:05:08	multiply force by the channel to the destination
0:05:11	um
0:05:12	the signal received at the E dropper again has the same structure where we have
0:05:16	a version of the
0:05:18	symbol is received at the dropper
0:05:20	uh once the jamming signal that we have
0:05:23	france
0:05:25	uh we have here the notation for the various vectors
0:05:29	and basically in this case the secrecy rate may be written in this form where the first
0:05:33	element here represents the rate
0:05:36	yeah to the destination
0:05:37	and the second to rake at T
0:05:41	um
0:05:42	as i said the the first uh
0:05:44	what that has been done on um
0:05:46	and this uh uh and is assumed that
0:05:49	or and
0:05:51	a really are called right
0:05:53	the G
0:05:54	and for this and really is
0:05:57	uh a are the power
0:05:59	uh the power P S and the vector or all the weights vector
0:06:03	uh only got
0:06:04	maybe be uh such that
0:06:06	yeah we get a maximum
0:06:08	sec receive and this is basically the optimization problem that
0:06:12	design
0:06:12	a P S O
0:06:14	oh make the
0:06:15	uh oh yeah O optimal
0:06:17	um
0:06:18	such that
0:06:20	that set was rate is
0:06:21	max
0:06:23	as we said were looking for more
0:06:25	uh energy efficient the uh weighting and we trying to minimize the number of really at
0:06:31	so we are basically um defining a racial and the threshold these is with here is the are sub S
0:06:36	a requirement
0:06:38	and we we uh define it as a fraction of the maximum a C rate that
0:06:44	so
0:06:44	if we are all K be eighty percent of a
0:06:46	that would be a zero point eight as we set this threshold
0:06:50	uh and therefore we
0:06:52	next we want to define an optimization problem that will help us identify
0:06:57	the best realise to use to get this accuracy rate which is the minimal one as well
0:07:04	uh to do so we first started um
0:07:07	um by introducing
0:07:09	a binary variable
0:07:12	and we just a vector Q where each element of this queue Q why
0:07:16	can be wanting to really
0:07:18	i exactly or zero if it's not
0:07:22	uh our objective eventually is to write it and that combinatorial uh a framework
0:07:26	and uh
0:07:28	uh yeah
0:07:29	and specifically in a knapsack problem yeah therefore we take
0:07:33	the original a sec receiver rate expression that we had before and we rewrite it so we can use it
0:07:39	in this frame
0:07:41	and we define um
0:07:43	are uh uh that the sec C rate
0:07:46	uh we
0:07:47	and E here
0:07:48	a out which is a uh a and X exponent um
0:07:53	function of the do what we can secrecy rate
0:07:55	and it a to be an expression and basically is a sum and high and J work Q one Q
0:08:00	J
0:08:01	uh
0:08:01	as you you know you recall from here basically represent present a really is T one and
0:08:08	uh in the um
0:08:10	uh jamming
0:08:11	um multiplies applies
0:08:12	a a function here are are i J
0:08:15	but are i J is you can see is a function of Q as well
0:08:19	uh so this uh F F of to here is is given here
0:08:23	and you can see to F age of Q and F G of Q
0:08:27	where the dependencies still and Q one Q J
0:08:30	which is given a general form here
0:08:33	uh so it's a nonlinear your function basically of Q i and Q
0:08:37	but this type of formulation now enables us to right
0:08:42	uh the search
0:08:43	uh
0:08:44	problem for the minimal set E as an that
0:08:48	and that six probably it means that we are trying to minimize
0:08:51	the number of element
0:08:53	or the cost of that element there are putting in and a
0:08:56	well at this is a are capacity this is what we want to go
0:09:00	and a and as i said it's a combinatorial optimisation problem Q why can be zero
0:09:06	um
0:09:07	as you can see when we use in here that can a sec receive a to are using it read
0:09:11	or my got a star and P star
0:09:14	to mean that we are using it with a
0:09:17	vector or a mean god that was to my
0:09:20	for the sec rate so
0:09:22	you can see here
0:09:23	but to basically uh do for a given set of Q let's say that we follow that we we
0:09:29	we are looking for Q when where
0:09:30	oh forwarding a possible solution for Q
0:09:33	for this Q we are going and optimising in and then P S
0:09:37	such that it maximises the set or C
0:09:41	uh so this is this is the do know um
0:09:44	and knapsack optimization problem
0:09:47	and
0:09:47	one of the well known problems all of this is that a complexity it it has an exponential complexity
0:09:53	uh it's uh
0:09:55	you for larger number of of of and it's
0:09:58	impossible possible to solve
0:10:00	so of course
0:10:01	to make it feasible and and usable they are looking for
0:10:04	a a fast approximation algorithm that was still be a fish
0:10:09	and um
0:10:10	in this work we have proposed a three different
0:10:13	uh
0:10:13	a approximation algorithms
0:10:16	each one has its advantages or disadvantages as we will discuss later
0:10:20	and each one has different the a level of complexity of course
0:10:25	uh the first one is uh
0:10:27	yeah individual sectors you rate than a base
0:10:30	really selection
0:10:31	uh
0:10:32	the second is a weighted norm really selection and the last one
0:10:37	is a successive a a really uh selection algorithm that is based on
0:10:41	what power uh start local search uh approach
0:10:46	um we start for the first one
0:10:47	the first one is is the
0:10:49	think five one
0:10:51	and what it it does it it relaxes the original position problem
0:10:56	and says we not going to optimize it's for each vector
0:10:59	what what are going to do we are going to
0:11:01	first take each individual really
0:11:05	are going to find a a
0:11:07	the optimal value for a i and P S time
0:11:11	that maximise the sectors C
0:11:12	for this uh a specific one
0:11:15	and
0:11:15	once we generate a set of uh of value
0:11:19	we are so like think the the we are successively selecting them by
0:11:23	they're value so we're selecting the highest one first and keep on adding
0:11:27	uh by there
0:11:29	and feel we we basically have some
0:11:31	uh um threshold uh pass
0:11:36	um
0:11:38	i don't note and how what what what is basically down we use this a figure to explain how
0:11:44	we basically find uh the the palm maximum um
0:11:48	oh values for P S and all my got to this process
0:11:52	and you have your plot for to to really
0:11:55	call really and really be
0:11:56	and you can see them
0:11:58	sec to see wait for each one of them as a function of the
0:12:01	of P S
0:12:02	and basically it it the the algorithm that to show identifies stills maximal point and the appropriate P S for
0:12:08	them
0:12:09	which are then used
0:12:11	a selection out
0:12:14	uh the second approach
0:12:16	yeah
0:12:17	is going if
0:12:18	first we went for the individual one here we going on the full system
0:12:22	so we assume we take all and really
0:12:24	and we doing what has been that in previous work which is optimising
0:12:28	the weight the vector or my guy and P S
0:12:30	such that the total
0:12:32	step C rate is all is met
0:12:35	no when not
0:12:36	repeating that that actually taking the values that we got
0:12:39	are this optimal value
0:12:41	and we are using them
0:12:43	in our uh expression for the set to see so yeah we not
0:12:47	calculate that again and again
0:12:49	so we're saving uh on this process
0:12:52	and uh we are selecting uh
0:12:55	uh the the the larger one of course which use a basically equivalent to
0:12:58	selecting the
0:13:00	uh i
0:13:01	a really is with their a larger storm and this is like like weighted norm uh
0:13:06	selection
0:13:09	the third one
0:13:10	does not assume any uh
0:13:13	relaxation on the original problem
0:13:15	that's on basically takes the we problem
0:13:18	and
0:13:20	is um
0:13:22	in a sense
0:13:23	in a greedy way
0:13:25	ah
0:13:25	and it's a a really is to the group
0:13:28	so we have a starting point
0:13:30	we we we start the let's say we do really one
0:13:34	and we keep and adding really
0:13:37	and each time we adding relays
0:13:40	we are we
0:13:41	going and maximizing uh the vectors
0:13:45	uh W and P again
0:13:47	and we are choosing the relay that
0:13:49	maximise the sec receiver in this case
0:13:53	now once we add a a a a a a ad
0:13:55	the the one that maximises with keep on adding and till we cross trash
0:14:00	uh
0:14:01	for a
0:14:02	a better performance in terms of of uh reading the optimum we we be
0:14:06	this search for every possible forced really
0:14:09	and this is one call
0:14:11	a most people start
0:14:12	yeah i am with people start a local search
0:14:16	uh
0:14:17	we eventually end up with them
0:14:20	and optimal solutions
0:14:22	and we choose the the one with the least number or
0:14:27	um
0:14:30	sure an example of that
0:14:32	uh
0:14:33	by the way the the here though optimization used done using um
0:14:38	an algorithm that was suppose to the proposed by um the at a bit trouble in web
0:14:44	and two thousand ten at each that
0:14:48	um um
0:14:49	to show uh an example of that
0:14:52	a you see C or scenario all of a source destination
0:14:56	and and you drop or or and we assume we have a set of relays
0:14:59	a a spreading a given area
0:15:02	ah
0:15:03	we assume fifteen uh really is are a given here
0:15:06	um and
0:15:09	uh we we normalize the sec to C rate compare sent to the maximum achievable one
0:15:14	and we we used to threshold one of them is ninety percent of zero point nine five and seventy five
0:15:19	percent
0:15:19	zero point somebody five
0:15:22	i you see for an example
0:15:24	of of the results that we get for this scenario
0:15:27	and
0:15:29	in in in black though it's not seen because the green is over that
0:15:33	and i and like to use a a is a uh the results of an exhaustive search
0:15:37	so basically if i would take for example for
0:15:40	really is
0:15:41	this points says
0:15:43	if i would do an exhaustive search for the best for really is this would be the the value the
0:15:47	to see way that that would get and so
0:15:50	and
0:15:51	the third on go with him a very nice we'd we'd the optimal one
0:15:56	uh uh we it for different scenario in in general it fold was very close to the optimal
0:16:01	uh it also more we'll bossed uh there there was information in paper it also more boss to the location
0:16:07	of the the sensors
0:16:09	respect to
0:16:10	if dropped or and
0:16:12	nation
0:16:13	uh in terms that it falls again candle
0:16:16	uh a the on a two
0:16:17	uh uh um
0:16:19	there are behaviour is more uh reliant on location
0:16:23	uh in many cases uh
0:16:25	as expected algorithm uh be performs better than algorithm a a a board to many have the stalls
0:16:31	slow reaction as you can see from here so
0:16:34	um uh for for low uh
0:16:37	low threshold if forms a we well but when the threshold is high as you can see here
0:16:42	it will give fifteen sensors or something like that
0:16:44	C right there
0:16:46	uh it would give sort twelve
0:16:48	a a sensor as the number of sensor that that we need for that
0:16:52	um
0:16:53	we also checked or robust most of that too small error in the estimation of the channel
0:16:58	uh between the source and you drop or
0:17:02	and uh again the the algorithm C is falling that before forming quite well in in uh in this sense
0:17:08	as well and most of them
0:17:10	a stay within a reasonable before
0:17:13	so to wrap things up uh
0:17:16	i the problem of selecting mean set of really seeing um
0:17:20	well wire score a cooperative system uh for the purpose of jamming
0:17:24	uh has been formulated as a knapsack problem
0:17:28	uh the first two algorithm of four or complexity all and uh
0:17:32	order of L
0:17:34	a while the um
0:17:35	the third one is
0:17:37	it's it's here
0:17:38	it sort of a a L
0:17:39	and time L and L is the number of a is we eventually end up
0:17:44	having in the subset
0:17:46	um
0:17:48	um
0:17:53	uh in terms of complexity what that explains is a little what this so uh in the sense that in
0:17:58	small or for smaller or uh on
0:18:00	a threshold
0:18:02	uh i'll go "'em" one free form relatively good but in large a threshold it you can perform as well
0:18:08	well do for like special algorithm be free phone
0:18:10	or not converge conversion to to the optimal one and you know the case as well
0:18:15	so there is a trade of your between performance of course and um
0:18:19	and complexity not to large trade off but there is a tradeoff
0:18:22	and
0:18:23	gives a few option of uh
0:18:25	uh
0:18:26	implementing that
0:18:27	in real
0:18:29	thank you

A KNAPSACK PROBLEM FORMULATION FOR RELAY SELECTION IN SECURE COOPERATIVE WIRELESS COMMUNICATION

Sensor Networks

Přednášející: Hana Godrichs, Autoři: Shuangyu Luo, Rutgers University, United States; Hana Godrich, Princeton University / Rutgers University, United States; Athina Petropulu, Rutgers University, United States; H. Vincent Poor, Princeton University, United States