当前位置：文档库 › Connected K-target coverage problem in wireless sensor networks with different observation scenarios

Connected K-target coverage problem in wireless sensor networks with different observation scenarios

Connected K -target coverage problem in wireless sensor networks with different observation scenarios q

Qun Zhao *,Mohan Gurusamy

Department of Electrical and Computer Engineering,National University of Singapore,Singapore

a r t i c l e i n f o Article history:

Received 24May 2007

Received in revised form 24March 2008Accepted 26March 2008

Available online 1April 2008Responsible Editor:Dr.F.Cuomo Keywords:

Wireless sensor networks Coverage Connectivity

Lifetime maximization Algorithms

Sensor activity scheduling

a b s t r a c t

In this paper,we consider the problem of scheduling sensor activities to maximize network lifetime while maintaining both discrete K -target coverage and network connectivity.In K -target coverage,it is required that each target should be simultaneously observed by at least K sensors.The data generated by the sensors will be transmitted to the sink node via single or multiple hop communications.As maintaining discrete target coverage cannot guarantee the network connectivity,we consider both target coverage and connectivity issues.Further,by adopting a more realistic energy consumption model,we consider the sensor activity scheduling problem and routing problem jointly.We study the problem with two observation scenarios depending on whether a sensor can distinguish the targets in its sensing area or not.For the ?rst scenario,a more general scenario where each sensor can simultaneously observe multiple targets is considered and we develop a polynomial-time algorithm which can achieve optimal solution based on linear programming and inte-ger theorem.For the second scenario,we show that the problem is NP-complete and develop an approximation algorithm for solving it.As the protocol cost of the optimal solu-tion and the approximation algorithm may be high in practice,we develop a low-cost heu-ristic algorithm which can be implemented in a distributed fashion for both scenarios.We demonstrate the effectiveness of the heuristic algorithm through extensive simulations.

1.Introduction

Recent advances in micro-electro-mechanical systems,digital electronics,and wireless communications have led to the emergence of wireless sensor networks (WSNs),which are comprised of a large number of sensing devices each capable of sensing,processing and transmitting.Applications of wireless sensor networks include battle-?eld surveillance,environmental monitoring,biological detection,smart spaces and industrial diagnostics [1].

Coverage determines how well an area of interest is monitored or tracked by sensors [2,3].There are broadly three types of coverage classi?ed based on what is to be

covered,namely area coverage,discrete points coverage and barrier coverage [2].This paper focuses on the discrete points (targets)coverage in a randomly deployed WSN where the density of sensor nodes is high to compensate for the lack of exact positioning.Discrete K -target coverage requires each target to be covered by at least K sensors simultaneously,which improves the accuracy and reliabil-ity of the observations [4]and is necessary for many appli-cations such as target classi?cation [5].

Connectivity concerns with delivering the observed-data from the source sensor to the destination (referred to as sink node )via radio transmissions.The transceiver of a sen-sor may be power controlled such that different transmis-sion power levels could be used to achieve different communication ranges .Multi-hop communications are needed when a sensor cannot reach the sink node directly.Therefore,sensors in a WSN may also serve as relays to forward other sensors’data to the remote destination.In

An earlier version of a part of this paper was presented at ICC 2007.*Corresponding author.Tel./fax:+6565165095.

E-mail addresses:zhaoqun@https://www.wendangku.net/doc/7c14589949.html,.sg (Q.Zhao),elegm@https://www.wendangku.net/doc/7c14589949.html,.sg (M.Gurusamy).

Computer Networks 52(2008)2205–2220

Contents lists available at ScienceDirect

Computer Networks

j o ur na l h om e pa ge :w w w.e ls e v ie r.c om /lo c at e/c om ne t

general,every activity of sensing,transmission and recep-tion consumes a certain amount of energy,and thus limits the network lifetime.

Network lifetime of a WSN de?nes how long the de-ployed WSN can function well.It can be de?ned as the per-iod from the time when the network was set up to the time when the WSN cannot guarantee certain coverage and/or connectivity requirements.As sensors are unattended de-vices with limited resources,network lifetime is one of the most important issues in WSNs.The network lifetime can be increased by scheduling only a subset of sensors necessary to be active,and let other sensors to sleep.The improved lifetime is achieved due to the reduced idle lis-tening,collisions of media access control(MAC)and traf?c load.

The problem of scheduling sensor activity to prolong the network lifetime while guaranteeing discrete target coverage has been studied earlier in[6–12].Based on dif-ferent sensor devices and applications,two observation scenarios have been discussed.In[6–9]each sensor node can observe all the targets in its sensing area,while in [11,12]each sensor node can select one and only one target in its sensing area to cover.However,most of the above works[6–9,11,12]do not consider the connectivity issue. In[13],it has been shown that network connectivity can be guaranteed if the complete area coverage is achieved and the communication range is at least twice the sensing range.However,this claim need not hold for the discrete points coverage problem as shown by an example in[10]. Further,the impact of communication energy consumed for sending the sensed data and relayed data on the sensor activity scheduling has not been given due consideration in the above works[6–12],since they either ignore the en-ergy consumption for data transmission or assume that each active sensor consumes the same amount of energy per unit time.However,in a practical scenario,the energy consumed by the active nodes can vary signi?cantly depending on the amount of sensed and relayed data. When the objective is to maximize the network lifetime, the impact of the existence of transmission bottleneck caused by multiple?ows traversing through the same re-lay node should not be neglected.In our work,we consider this more realistic scenario where the energy consumption of each node is calculated by the amount of data it senses, receives and transmits.Further,as the energy consumption of data communications is taken into account,the problem of scheduling sensor activity becomes non-trivial as it is jointly considered with the routing problem,that is,be-sides selecting as small number of active sensors as possi-ble,we need to select the set of active sensors such that the route from each sensing node to the sink is as energy ef?-cient as possible.Finally,solutions developed in[11,12] considers only the case when each sensor can select one and only one target.Since sensors may have the capability to sense multiple targets simultaneously,new solutions need to be developed for this more general case.The solu-tion developed in[11,12]cannot be trivially extended to this general case.

In this paper,we discuss the problem of scheduling sen-sor activity while maintaining both discrete K-target cov-erage and network connectivity.We model the problem as Lifetime Maximization Observation Schedule(LMOS) problem and study the problem for two different observa-tion scenarios(LMOS-1and LMOS-2).In the?rst scenario (LMOS-1)each active sensor can distinguish targets and select up to L targets in its sensing area to observe,while in the second scenario each active sensor simultaneously observes all the targets in its sensing area.We develop a polynomial-time algorithm that achieves the optimal solu-tion for the LMOS-1problem.We show that the LMOS-2 problem is NP-complete and develop an approximation algorithm for solving it.As a practical implementation we develop a much faster?exible heuristic algorithm which can be implemented in a distributed fashion called Communication Weighted Observation Scheduling(CWOS) for both scenarios.The CWOS algorithm uses a greedy method to select the set of source nodes(called source set)that cover all the targets and it couples the communi-cation cost and the selection of source sets.

Our work is useful for the kinds of applications such as surveillance or environment data collection where?xed points or locations are required to be monitored,espe-cially when the targets spread in an area and each de-ployed sensor has multiple targets in its sensing area. This can happen in applications where a cluster of sensors is casually deployed around a cluster of geographically-nearby targets.Further,our work is also useful in applica-tions such as battle?eld surveillance where the exact locations of targets e.g.the animal nets or the hidden en-emy constructions,may not be known in advance and the deterministic deployment of sensors is prohibitive.The sensors have to be randomly deployed into the susceptible area,where they recognize the targets,observe them and send the observation data back to the sink via multi-hop communications.Discrete K-target coverage improves the accuracy and reliability of the observations[4]and is necessary for many applications such as target classi?ca-tion[5].

The contribution of our work is four-fold.

1.We study the connectivity issue and consider the com-

munication energy consumption in the network.We consider the impact of communication energy con-sumed for sending the sensed data and relayed data on the sensor activity scheduling.

2.Unlike in[11,12],we make a more general assumption

for LMOS-1problem that each sensor can freely select up to L targets in its sensing area to observe.We pro-pose a new polynomial-time algorithm based on linear programming and integer?ow theorem[14,p.666]to optimally solve the LMOS-1problem.

3.We derive an upper bound and lower bound for the

LMOS-2problem based on the optimal solution of LMOS-1problem.An approximation algorithm is devel-oped for LMOS-2problem which provides insights into the LMOS problem and can be used to evaluate the per-formance of other algorithms.

4.We develop a?exible low-cost heuristic which can be

implemented in a distributed fashion to solve the LMOS problem for both scenarios.We carry out extensive simulations to demonstrate the effectiveness of the pro-posed heuristic algorithm by comparing its perfor-

2206Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–2220

mance with that of the optimal solution for the LMOS-1 problem and the approximation algorithm for the LMOS-2problem.

The rest of the paper is organized as follows.In Section 2,we brie?y describe the related work.In Section3we introduce the system model and give the de?nition of LMOS problem.In Section4,we develop a polynomial-time algorithm for LMOS-1problem and prove its correctness. In Section5we show that LMOS-2problem is NP-Complete and present the approximation algorithm for it.The pro-posed CWOS heuristic algorithm is presented in Section 6.In Section7,performance study is carried out and the re-sults are discussed.Section8concludes this paper.

2.Related work

Scheduling sensor activity while guaranteeing a certain coverage requirement to prolong the network lifetime has been studied in the literature(see e.g.[15]for a survey and references therein).The coverage requirements that are commonly considered include(complete or partial)area coverage and complete target coverage.Barrier coverage is another type of coverage problem but the objective is to minimize the probability of undetected intrusion through the barrier[16,17].The problem of scheduling sensor activities for complete area coverage is addressed in[13,18–23].Maintaining partial(but high)area coverage is discussed in[24–26].Here,we brie?y review some re-cent advances on scheduling sensor activity to cover dis-crete targets[6–10,27].

In[6],an algorithm to?nd discrete sensor covers each providing complete area coverage is proposed without considering network connectivity.In[7],Cardei et al.mod-eled the discrete target coverage problem as a disjoint set cover problem which is proven to be NP-Complete.In[8], Cardei et al.extended their work in[7]and argued that the network lifetime can be further improved without the constraint that the selected set covers are disjoint, i.e.,a sensor may appear in different covers.In[9],Cardei further extended their work on discrete target coverage by assuming that sensors have adjustable sensing ranges. However,connectivity is not considered in[7–9].In[10], Lu et al.schedule sensor activity by self-con?guring sens-ing range,in the environment where both discrete target coverage and connectivity are satis?ed.However,only sensing power is taken into account in their energy con-sumption model.Further,the heuristic proposed in[10] maintains network-wide connectivity which may not be necessary for target coverage.In fact,only those sensors along the routes carrying the sensed data are required to be active.

In[11]the authors assume that each sensor can freely select the target to observe and observe only one target at each time.With this assumption,the authors proposed an optimal solution based on linear programming and combinational matrix theory to?nd the target observation schedule that achieves the maximum network lifetime. The authors extended their results to the situation when each target is required to be covered by at least K sensors (K-target coverage)in[12].However,the connectivity is-sue is not addressed in[11,12].Further,the observation assumption used in[11,12]is only a special case of the observation scenario discussed in our work.

Maximizing network lifetime is an important issue in wireless sensor networks.In[28],the authors formulated the routing problem as a linear programming problem, where the objective is to maximize the network lifetime, which is equivalent to the time until the network parti-tion occurs due to battery outage,and proposed a mini-mum cost path routing algorithm to prolong the network lifetime.In[29],the authors provided upper bounds on the lifetime of a sensor network by taking into account all the possible collaborative data gathering strat-egies over the possible network routes.The Maximum Lifetime Data Aggregation(MLDA)and Maximum Lifetime Data Routing(MLDR)problem[30]were also studied and solved as the LP problem.In[31],the maximum data col-lection problem was formulated as a LP problem and an approximation algorithm was developed.However,all the above lifetime maximization techniques are based on a communication network graph and they do not ad-dress the issue of network coverage and scheduling sen-sors activities.

Our work differs from other related works in that we consider coverage and connectivity issues and more importantly,the impact of the communication energy con-sumed for transmitting sensed data as well as relayed data on sensor activity scheduling.Further,we consider a more general problem(LMOS-1)wherein each sensor can freely select up to L targets in its sensing area.

3.System model and problem description

We consider the following application scenario.In the sensing?eld,a number of sensors are randomly scattered to continuously observe a number of?xed targets and re-port the observed data to the sink node periodically via radio communications.Each target is required to be simul-taneously observed by at least K sensors at any time.A sen-sor node which is assigned observation task to observe the targets is called a source node.A source node generates data messages at a certain rate,and transmits these data messages to the sink node via single or multi-hop commu-nications.The rate at which data messages are generated by a source is assumed to be related to the set of targets observed by the source.A sensor node which does not per-form observation task but is assigned relay task to relay data from the sources to the sink is called a relay node. Both the source sensors and relay sensors are called ‘‘active”sensors.Other sensors with no tasks go into ‘‘sleep”state to avoid wasting battery energy.Sensors are assumed to be unattended and have?nite battery energy. Any activity of sensing,transmitting or receiving consumes battery energy of a sensor,and thus limits the running time of the network.In our work,we determine the state of all the deployed sensors to be either active(source or re-lay or both)or sleep as well as the state durations,such that the network lifetime is maximized.The network lifetime is de?ned as the time duration starting from network set up to the time when the sink can no longer receive the re-quired observation reports of all the targets.

Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–22202207

Depending on the sensor devices and applications,we consider the following two different observation scenarios (OS)regarding the observation of targets by a source sensor:

OS-1An observing sensor can distinguish the targets in its sensing area and select a subset of targets to

observe.For example,an image sensor with adjust-

able angle of view can choose and focus on only a

number of targets in its sensing range.

OS-2An observing sensor should simultaneously observe all the targets in its sensing area because it cannot

distinguish targets.For example,a?sheye lens

(wide-angle lens)image sensor with?xed observa-

tion angle will observe and report all the targets in

its sensing area simultaneously.

In OS-1,we set an integer L as the maximum number of targets a sensor can simultaneously observe.When L?1, each sensor can only observe one target at a time.

We assume without loss of generality that the whole network lifetime is slotted into a series of time slots. Within each time slot the state(observation,relay or sleeping)of each node does not change.An observation assignment determines the state of each node in a time slot.The overall duration of the time slots with the same observation assignment is called the operation duration of the observation assignment.For OS-1,an observation assignment should include the set of source nodes and re-lay nodes,the subset of targets to be observed by each source node and the path from each source to the sink (via only active nodes);For OS-2,it should include the set of source nodes and relay nodes together with the path from each source to the sink.Let S?f s1;...;s N g de-

note the set of sensor nodes,j S j?N;P?f p

1;...;p

g de-

note the set of targets,j P j?M;R denote the sink node.

Further we de?ne a communication linkes i;s jTexists if sensor s i is in the communication range of sensor s j,and an observation linkep

;s jTexists if target p m is in the sensing area of sensor s j.Thus graph G?f S[P[R;E g builds the topology of the network,where E contains all the communication links and observation links.On graph G,an observation assignment/in OS-1is de?ned as a set of paths starting from the target set to the sink node.All the sensors on the paths are‘‘active”nodes.For each path,

the starting observation linkep

;s iTrepresents that sensor

s i is assigned as a source to observe target p

,and the

observation data of p

will be transmitted by s i to the sink through the path.On the other hand an observation assignment/in OS-2is de?ned as a set of paths from the source set to the sink node.All the sensors on the paths are‘‘active”nodes.For each path,the starting node is the source node which transmits the observation data of all the targets in its sensing area to the sink through the path.

For OS-1,an observation assignment is called feasible if the K-target coverage requirement is satis?ed,no observa-tion link is selected more than once and no sensor is selected as the source sensor on more than L paths.For OS-2,an observation assignment is called feasible if the K-target coverage requirement is satis?ed.

We de?ne an observation schedule as a sequence of

observation assignments with their operation durations. An observation schedule is called feasible if and only if all the observation assignments in the schedule are feasible and each node consumes energy less than its initial energy after the execution of the schedule.

A target rate r m is de?ned for each target p

as the observation data reporting rate.The data rate outgoing from a source is the sum of the target rates of the targets it is observing,which is called as source rate.We consider the following energy consumption model which mainly takes into account the energy consumption for sensing and relaying data.Let e s and e r denote the energy con-

sumed for sensing and receiving a bit,respectively.Let e t

ij denote the energy consumed by sender s i for transmitting a bit to receiver s j:e t

?e ttbád a

,where e t and b are con-stants,d ij is the Euclidean distance between node s i and s j and a is the path loss factor.

The Lifetime Maximization Observation Schedule (LMOS)problem is de?ned below:

De?nition1(LMOS problem).Given a graph G?f S[ P[R;E g,target rate set f r m g,coverage requirement K, the initial energy E0es iTfor each sensor s i,?nd a feasible sensor observation schedule,which has the maximum total execution time T(i.e.maximum lifetime).

In the following sections,we use LMOS-1to refer to the LMOS problem for OS-1and LMOS-2to refer to the LMOS problem for OS-2.

4.LMOS-1problem

4.1.LP formulation for LMOS-1problem

Let s im denote the overall time duration that sensor s i is

assigned to observe target p

,i.e.the period during which

observation linkep

;s iTis selected in all the observation assignments.Let F ij denote the total amount of data tra-versing through linkes i;s jT.Let T denote the network life-time.The following LP formulation gives an upper bound on the maximum network lifetime of LMOS-1problem: Objective:

Maximize:Te1T

Subject to:s im6T8es i;p

T;e2TX

s im6LT8s i;e3T

s im?KT8p m;e4T

s im r mt

j?i

F ji?

j?i

F ij8s i;e5T

s im r m e st

j?i

eF ij e t

tF ji e rT6E0es iT8s i:e6T

In the above formulation,Eq.(2)imposes that the overall time duration that a sensor observes a target should be less than the network lifetime,because no observation link can be selected more than once in an observation assignment. Eq.(3)imposes that the sum of the time durations that a sensor observes the targets should be at most L times the network lifetime,because each sensor can simultaneously

2208Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–2220

observe up to L targets.Eq.(4)imposes that the sum of time durations that each target is observed should be K times of the network lifetime due to the K -target coverage requirements.Eq.(5)imposes the ?ow conservation and Eq.(6)imposes the energy consumption constraint.

Since the constraints in the LP problem are only neces-sary conditions (i.e.an observation link can still be selected more than once in an assignment even when Eq.(2)satis-?es),the solution of the above LP problem provides a life-time upper bound for the LMOS-1problem.Further,the optimal observation schedule is not given in the LP solu-tion.To completely solve the LMOS-1problem,in the next sections,we develop a polynomial-time algorithm which ?nds a feasible observation schedule achieving the same network lifetime as given by the LP solution,and thus prove that the solution of LP problem gives exactly the optimal lifetime of LMOS-1problem.4.2.Algorithm description

In this section we describe the algorithm we developed to build the optimal observation schedule.The input of the algorithm is the optimal solution obtained by solving the LP problem f T ;f s im :8es i ;p m Tg ;f F ij :8es i ;s j Tgg .The output is the desired optimal observation schedule f /ex T;s ex T:16x 6X g ,where X is the number of observation assign-ments,each /ex Tis a feasible observation assignment in the schedule and s ex Tis the corresponding operation dura-tion of the assignment.

For each feasible observation assignment /ex T,given its operation duration s ex T,we can calculate the amount of time that each observation link ep m ;s i Tis occupied in the duration –s im ex T,as well as the amount of ?ow traversing through each communication link es i ;s j T–F ij ex Tas follows:

s im ex T?

s ex T;ep m ;s i T2/ex T;

0;ep m ;s i T2/ex T;

e7TF ij ex T?X

m :es i ;s j T2R m ex T

r m s ex T;e8T

where R m ex Tis the route in /ex Tfrom target p m to the sink.If all the assignments in a schedule are feasible observa-tion assignments,together with P x s ex T?T ,P

x s im ex T?s im

and P

x F ij ex T?F ij (where T ,s im and F ij are elements in the solution set),we can conclude that the schedule is the de-sired optimal schedule.Let us call f s ex T,f s im ex T:8es i ;p m Tg ,f F ij ex T:8es i ;s j Tgg as the x th assignment solution.

The pseudo-code of the algorithm is described in Table

1.The algorithm runs in iterations.In each iteration x ,a feasible assignment /ex Twith proper operation duration s ex Tis found based on the solution set,and then the solu-tion set f T ;s im ;F ij g is updated by decreasing the assign-ment solution f s ex T;s im ex T;F ij ex Tg .Next we introduce how to ?nd the assignment and its operation duration in each iteration,and prove its correctness.

In the x th iteration,given the current solution set f T ;s im ;F ij g ,we ?rst build a ?ow network G ??f V ?;E ?g as shown in Fig.1(line 3).The graph consists of all the obser-vation links ep m ;s i Twith non zero s im together with the tar-gets and sensors connected by those links.Let E ?o denote

these observation links,S ?

denotes these sensors and P ?

denote these targets.Further,a pseudo -target ^p

is added in G ?

with pseudo -observation links connecting to all the sensors in S ?.We de?ne s i ^p ?T ed r i e àr i Tas the pseudo -observation duration that each sensor s i observes ^p

,where r i ?P

m s im =T .A source node s is added with links connect-ing all the targets in P [^p

;a destination node t is added with links connecting all the sensors in S ?.Unit capacity is assigned to each link in E ?o .The capacity of the link from s to each target p m is set to be K .For each link from sensor s i to the destination t ,the capacity is set to

be d r i e .For each link from the pseudo-target ^p

to the sensor s i ,the capacity is set to be 0if r i ?d r i e ,otherwise 1.

Table 1

Fig.1.Flow network G ??f V ?;E ?g .

Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–22202209

The capacity of link es ;^p

Tis set to be P

i ed r i e àr i T.Now we complete the building of ?ow network G ?.

A sensor may observe different number of targets in dif-ferent observation assignments.If sensor s i observes the same number of targets during the whole network lifetime,say d r i e ,the sum of its observation time would be d r i e T .Thus ed r i e àr i TT de?nes the maximum duration for which sensor s i can observe less than d r i e targets,otherwise the sensor must observe more than d r i e targets in some other durations,and thus may violate the observation constraint that each sensor can observe up to L targets.The introduction of pseudo-target avoids violating the above observation constraint by setting the pseudo-observation duration and letting the sensor observing less than d r i e number of targets to observe the pseudo-target.Each sen-sor s i observes exactly d r i e targets (including the pseudo-target)in the whole network lifetime (as shown later in Section 4.3).

In graph G ?,each link between a sensor (pseudo)target pair implies that the sensor should observe the (pseudo)target for some duration of time in the subsequent observation assignments.The observation relationship in an assignment can thus be represented by a ?ow from source s to the destination t with each traversed observa-tion link is selected in the assignment.The ?ow can be pro-ven to be a maximum ?ow as shown later in Section 4.3.Therefore,the desired observation assignment can be con-structed by ?nding the corresponding maximum ?ow on graph G ?.The detailed explanation is given below.

Let E 0o denote the set of the observation links ep m ;s i Ton which s im ?T .Clearly these links should be selected in all the subsequent assignments and E 0o E ?o .For each obser-vation link ep m ;s i T2E 0

o ,we delete the link ep m ;s i Tfrom the G ?,and in turn decrease the capacity of links es ;p m Tand es i ;t Tby 1,respectively.After deleting all the links with zero capacity we construct a new ?ow network G 0(line 4).Using Ford–Fulkerson method [14],we ?nd a

maximum ?ow f on G 0(line 5).Let E f o and E f

p denote the set of observation links and pseudo-observation links on which ?ow f is positive,respectively.We construct the set of observation links in the observation assignment

as E /o ?E 0o [E f

o (line 6).

For each observation link ep m ;s i T2E /o ,we ?nd a path from s i to the sink via only communication links with F ij >0(https://www.wendangku.net/doc/7c14589949.html,ing breadth ?rst search)(line 7).Appending each observation link ep m ;s i T2E /o with the path,we build an observation assignment /ex T(line 8).

After building the observation assignment /ex T,we can determine the operation duration s ex T.The value of s ex Tis chosen as the maximum value while satisfying the follow-ing four conditions:(a)F ij ex T6F ij for any communication link es i ;s j T2/;(b)s im ex T6s im for any observation link ep m ;s i T2E /o ;(c)T às ex TP max es im :ep m ;s i T2E /o T;

(d)s ex T6s i ^p for any pseudo-observation link e^p

;s i T2E f p .(Re-call that E f

p denote the set of pseudo-observation links on which the maximum ?ow f is positive).Let s c min denote the minimum value of F ij =P

m :es i ;s j T2R m ex Tr m on each selected communication links es i ;s j T;s o min denote the minimum va-lue of s im for observation links in E /o ;s p min denote the mini-mum value of s i ^p for pseudo-observation links in E f p ;and s 0max denote the maximum value of s im for observation links

in E ?o àE /

o .The operation duration of assignment /is set (line 9)as

s ex T?min es o min ;s p min ;s c min ;T às 0

max T:

e9T

Then we calculate the x th assignment solution f s ex T,s im ex T,F ij ex Tg and update the solution set f T ;s im ;F ij g by decreasing it by the assignment solution (line 10).If the value of T be-comes zero in the updated solution set,the algorithm stops.

4.3.Correctness of the algorithm

Theorem 1.The solution set f T ;s im ;F ij g in each iteration satis?es the following equations:s im 6T 8es i ;p m T;e10TX

s im 6LT 8s i ;e11TX

i s im ?KT 8p m ;e12T

X m s im r m t

j ?i

F ji ?

j ?i

F ij

8s i ;e13Ts im P 0;T P 0;F ij P 0

8s i ;s j ;p m :

e14T

Proof.We prove the theorem by induction.In the ?rst iteration,as the solution set is the solution of the LP prob-lem,all the equations are satis?ed.

Suppose that the equations are satis?ed in the x th

iteration.Let f T x ;s x im ;F x

ij g denote the solution set in the

iteration and f T x t1;s x t1

im ;F x t1ij g denote the solution set in the next iteration.From the description of the algorithm,we have

T x t1?T x às ex T;

e15Ts x t1im ?s x

im às ex T;ep m ;s i T2E /o ;s x

im ;ep m ;s i T2E /o ;

e16TF x t1ij ?F x ij àF ij ex T;

e17T

From Eqs.(15)and (16),for observation links in E /o ,we

have s x t1im 6T x t1.As s ex T6T x às 0

max ,for observation links

not in E /o ,we also have s x t1

im 6T x t1.Thus Eq.(10)is satis?ed in the x t1th iteration.

As s ex T6s o min and s ex T6s c

min ,we have s x t1im P 0and F x t1ij

P 0.As Eq.(10)is satis?ed in the x t1th iteration,T x t1P s x t1

im P 0.Eq.(14)is satis?ed in the x t1th iteration.

Consider the ?ow network G ?we constructed.The

capacity on all the links except link es ;^p

Tare integer values (K ,1or d r i e ).As Eq.(12)is satis?ed in the x th iteration,

the capacity of link es ;^p Tis P i ed r i e àr i T?P

i d r i eàP i P m s x im =T x

?P i d r i e àKM ,which is also an integer value.Thus the capacity of all the links in G ?are integer values.In turn,the capacity of all the links in G 0are also integer values as we build G 0from G ?.Let n denote the number of

links in E 0o (links with s x im ?T x

which are deleted from G ?);n i denote the number of links in E 0o connecting with s i ;n m denote the number of links in E 0o connecting with p m .For

each sensor s i ,as r i ?P m s x im =T x

,n i 6d r i e ,the capacity of link es i ;t Ton G 0is given by d r i e àn i P 0.For each target p m ,from Eq.(12),we infer n m 6K ,and the capacity of link

2210Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–2220

es ;p m Tis K àn m P 0.Therefore,the capacity of each link in G 0is a non-negative integer.

It is easy to prove that the capacity of G 0is P

i d r i e àn ,

the set of links fes ;p m T:8p m g [es ;^p

Tand fes i ;t T:8s i g are both minimum cuts of G 0

.Therefore,the value of the

maximum ?ow f is also P

i d r i e àn .In addition,as all the links in G 0have non-negative integer capacity,from Integer Theorem [14,p.666],the value of f on all the link are also integer values.Since unit capacity is assigned to all the observation links and pseudo-observation links, f can only take a value of 0or 1on these links.As the set of links

fes ;p m T:8p m g [es ;^p

Tis the minimum cuts of G 0,the value of ?ow f on each link es ;p m Tis the capacity on the link.

From ?ow conservation,we have P

i f mi ?K àn m .Since f

only take 0or 1values on observation links,P i

f mi is the

number of links in E f o connecting with p m .As E /o ?E 0

o [E f o ,from Eq.(16),we have X i s x t1im

s x im à

f mi tn m !

s ex T?K eT x às ex TT?KT x t1

e18T

and thus Eq.(12)is satis?ed in x t1th iteration.

As the set of links fes i ;t T:8s i g is also the minimum cut of G 0,the value of ?ow f on each link es i ;t Tis the capacity

on the link.From ?ow conservation,we have P m

f mi t

f ^p i ?d r i e àn i .From s ex T6s p min ,we have s ex T6s i ^p

?ed r i e àr i TT x

.Consequently,we have

X m

s x t1im

?X m

s x im

àX

f mi

tn i

s ex T?r x iT

àed r i

e à

f ^p i

Ts ex T

?d r i eeT x às ex TTàed r i e àr i TT x ts ex T f ^p i 6d r i e T

x t1

6LT x t1

and thus Eq.(11)is satis?ed in x t1th iteration.

From Eqs.(7)and (8),if Eq.(13)is satis?ed in x th iteration,it is still satis?ed in x t1th iteration.

Thus the theorem is proved.h Corollary 1.In each iteration,for each observation link ep m ;s i T2E /o ,there exists a path from s i to the sink via only communication links with F ij >0.

Proof.As Eq.(13)is satis?ed in each iteration (?ow con-servation),for each sensor s i 2S ?(the sensor with s im >0),there must exist a route from s i to the sink via only links with F ij >0.As the set of sensors connected by E /o is a subset of S ?,the corollary is proved.h

Corollary 2.The observation assignment built in each itera-tion is feasible observation assignment.

Proof.In the proof of Theorem 1,we have P

i f mi ?K àn m

in each iteration.As f can only take 0or 1values on

observation links,there are K àn m sensors selected to observe target p m in E f o .Since there are n m sensors selected to observes target p m in E 0o ,E 0o \E f o ?/and E /o ?E 0o [E f

o ,there are totally K sensors selected to observe each target p m in the observation assignment built in each iteration.

Also,we have P

m f mi t f ^p i ?d r i e àn i in each iteration.Each sensor s i can observe at most d r i e àn i targets in E f o and n i targets in E 0o .As Eq.(11)is satis?ed in each iteration,we have d r i e 6L .Each sensor s i can observe at most L targets in the observation assignment built in each iteration.

Finally,as corollary 1,we can ?nd a route from each selected source node to the sink,e.g.via breath-?rst or depth-?rst search.Therefore,the observation assignment built in each iteration is feasible.Hence it is proved.h Lemma 1.In each iteration x,if T >0,we have s ex T>0.Proof.The operation duration s ex Ttakes one of the follow-ing four values:s o min ;s p min ;s c min ;T às 0

max .As G ?contains only observation links with non-zero s im ,we have s o min >0.As

all the observation links with s x

im ?T x are selected into the observation assignment,we have s 0max 0.As the route from each source node to

the sink is built by links with F x ij >0,we have s c

min >0.Hence it is proved.h

Theorem 2.The decomposition algorithm terminates in at

most N eM t1TtN 2t1iterations with P

x s ex T?T and has polynomial-time worst case time complexity.

Proof.In any iteration x ,the operation duration s ex Ttakes

one of the following four values:s o min ;s p min ;s c min ;T às 0

max .If

s ex T?s c min ,at least one positive element F x

ij >0in the solu-tion set is updated to be F x t1

ij ?0.If s ex T?s o min ,at least one

positive element s x

im >0in the solution set is updated to be s x t1im ?0.

If s ex T?T às 0max ,at least one element s x im

in the

solution set is updated to be s x t1

im ?T

x t1.If we have s x

im ?T x in the x th iteration,as link ep m ;s i Twill be selected

in the observation assignment,we have s x t1

?T x t1in the x t1th iteration,and thus we have s z im ?T z

in all the iterations with z >x .

If s ex T?s p min ,let s i be the sensor that has s i ^p ?s p

min .From the de?nition of s p min we have f ^p i ?1.As P m f mi t f ^p i ?d r i e àn i ,from Eqs.(16)and (15),we have X

s x t1

im ?

m s x im à

f mi tn i !

s ex T

?r i T x

ts ex Tàd r i e T x td r i eeT x às ex TT

?s ex Tàs i ^p td r i e T

x t1

?d r i e T x t1:And thus at least one sensor s i with s i p >0in the x th iter-ation has s i p ?0in the x t1th iteration.If a sensor s i has

s i p ?0in the x th iteration,as f ^p i

?0,we have r i ?d r i e and P m f mi ?d r i e àn i ,and thus we have P m s x t1

im ?

d r i

e T x t1

.Sensor s i has s i p ?0in all the following iterations z >x .

As there are at most N 2communication links,at most NM observation links and at most N pseudo-observation links,the algorithm will stop in at most N eM t1TtN 2t1iterations.As the maximum ?ow on graph G 0is at most KM tN ,the time complexity of Ford–Fulkerson algorithm is O eKM 2N tMN 2T[14].The time complexity of bread-?rst

Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–22202211

search to ?nd path from each source to the sink node is O eN 3T.Therefore,the time complexity of the decomposi-tion algorithm is O eN 2eKM 2tMN tN 2TeM tN TT.From Corollary 2and Lemma 1,the algorithm will continuously generate feasible observation assignments and non-zero operation duration until T ?0.As after each iteration T is

updated by decreasing s ex T,we have P

x s ex T?T .h Theorem 3.The observation schedule constructed by the decomposition algorithm is feasible and the solution of the LP problem gives the optimal lifetime of LMOS problem.Proof.The algorithm stops when T ?0.From Eqs.(10)and (13),we have s im ?0and F ij ?0when T ?0,and thus we

have P x s x im ?s im and

P x F x

ij ?F ij .From Eq.(6)we can con-clude that the energy consumption of each node s i after executing the constructed schedule is less equal to E 0es i T.Since each observation assignment in the schedule is feasi-ble (corollary 2),the constructed observation schedule is feasible.

As the LP solution gives an upper bound of the optimal lifetime of LMOS problem,and we can ?nd an feasible observation schedule (solution of LMOS problem)that achieves this upper bound,the solution of the LP problem gives the optimal lifetime of LMOS problem.h 5.LMOS-2problem

We can prove LMOS-22NP by verifying in polynomial time whether a non-deterministically selected observation schedule is feasible.Further,LMOS-2problem can be proven to be a NP-Complete problem as the Maximum Set Covers (MSC)problem [8],which has been proven to be NP-com-plete,is a special case of LMOS-2problem when (1)each node communicates directly with the sink node,(2)K ?1

and (3)ee s te t i R T

p m 2P i r m is the same for each sensor s i ,where P i is the set of targets that are in the sensing area of sensor s i .Since LMOS-2problem is NP-complete,there does not exist polynomial-time algorithm to achieve the optimal solution unless P ?NP .This motivates us to devel-op an approximation algorithm for LMOS-2problem.In this section we develop an approximation algorithm for LMOS-2problem.The analysis of approximation ratio proceeds as the Garg–Konemann algorithm [32].5.1.Upper bound and lower bound

Given an instance of LMOS-2problem,we can build an instance of LMOS-1problem with the same initial require-ments and L ?1.Let T 1denote the optimal lifetime of the LMOS-1instance and let T 2denote the optimal lifetime of

the LMOS-2instance.let M ?max i max m 2P i P m 2P i

r m

.We

make the following claim.

Claim 1.T 1P T 2P 1

M T 1.

Proof.Given any feasible solution of the LMOS-2instance

with lifetime T 2,we could build a feasible solution of the corresponding LMOS-1instance with lifetime T 2by build-ing the same observation assignments and setting the

same operation durations as in the solution of LMOS-2

and assigning each source node to observe all the targets in it sensing area since L ?inf.Thus we have T 1P T 2.Given any feasible solution of the LMOS-1instance with lifetime T 1,we could build a feasible solution of the LMOS-2instance by assigning the same set of source nodes as in the solution of LMOS-1instance.The data generated by each node in LMOS-2solution is at most M times of that in LMOS-1solution,and thus we have

T 2P 1

T 1.h 5.2.LP packing formulation and dual problem

Given an instance of the LMOS-2problem,let us enu-merate all the possible set of sources U ?f U 1;U 2;...;U Q g in the feasible solution of the instance,such that each set U q 2U contains observing sensors that can cover all the targets for at least K times.Thus,the source set of any observation assignment in the feasible solution of the LMOS-2problem would be in U .Let R denote the sink node;let s q denote the duration that U q is selected as the source set to observe the targets,where q denotes the index of source set in U ;Let F s i denote the total amount of data that are generated by node s i when it is selected as the source node;Let N i denote the set of neighbors of sensor s i ;Let X iq be 1if node s i belongs to the source set U q ,otherwise 0.We also use the notations as given in Section 4.The LMOS-2problem can be formulated as follows:

Maximize :X

16q 6Q

s q e19T

X 16q 6Q

X iq á

m 2P i

r m s q àF s i ?08s i 2S ;e20Tà

j 2N i

F ij t

j 2N i

F ji tF s i àF i R ?08s i 2S ;

e21TX

j 2N i

F ij e t ij t

j 2N i

F ji e r tF s i e s i tF i R e t

i R 6E 0es i T

e22T8s i 2S :

e23T

Eqs.(20)and (21)are the ?ow conservation constraints.Eq.

(23)is the energy consumption constraint.The dual prob-lem of the above LP problem is as follows:

Minimize :X

16i 6N

c i E 0es i Te24T

àa i ta j te t ij c i te r c j P 08i ?j ;s j 2N i ;e25Te t i R c i àa i P 08s i 2N R ;

e26Tàb i ta i t

e s i c i

P 0816i 6N ;e27TX 16i 6N

X iq X m 2P i

r m áb i P 1816q 6Q ;

e28T

where a i ;b i ;c i P 0(16i 6N )are variables in the dual problem.The dual problem can be interpreted as a prob-lem of assigning weights to the links in the network.Next we de?ne the link weight,node weight and path weight,and then rewrite the dual problem.Let ~C be the vector such that its i th element is c i .We de-?ne the objective function of the dual problem as

D e~C T?X

c i E 0es i T:e29T

2212Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–2220

In addition,we de?ne the link weight w ij e~C Tfor each com-munication link es i ;s j T2E and node weight w i e~C Tfor each sensor s i in the original LMOS-2problem:

w ij e~C T?e t ij c i te r c j

if j ?R ;es i ;s j T2E ;e t i R c i if j ?R ;es i ;R T2E ;(

e30T

w i e~C T?e s i c i

8s i 2S :

e31T

Consider an arbitrary path P from node s i to the sink R .Let

P be f s i ;n 1;n 2;...;n l ;R g ,we de?ne the path weight of P w P e~C Tas the sum of node weight w s i e~C Tand link weights on the https://www.wendangku.net/doc/7c14589949.html,ing Eqs.(25)–(27),we have w P e~C TP b i .

Let w i SPT e~C Tdenote the path weight of the shortest path (path with the minimum path weight)from node s i to the https://www.wendangku.net/doc/7c14589949.html,ing Eq.(28),we de?ne a e~C T?min 16q 6Q f P i X iq P m 2P i r m áw i SPT e~C Tg P 1.The dual problem is then equivalent to assigning values to ~C such that D e~C T=a e~C Tis

minimized subject to the constraint that a e~C TP 1.Let b ?min D e~C T

a e~C Tn o

.5.3.Algorithm description

The above interpretation of the dual LP problem leads to our approximation algorithm,which is described in Table 2.

The output of the algorithm are L ,/t k and s t

k ,which are the network lifetime,observation assignments and their operation durations,respectively.At the beginning,we scale the problem such that b P 1(line 1).This scaling is useful for our analysis for approximation ratio as explained later.We then set the initial value for d ,k and c i (line 2).The algorithm then proceeds in iterations and terminates when D e~C T>1.Let us call each outer loop (lines 3–17)as an iteration which is indexed by t ,and call each inner loop (lines 5–14)as a phase in the iteration which is indexed by k .The duration of each iteration is ?xed as s p .Each iteration may be composed of multiple phases.In each phase,an observation assignment /t k to-gether with its operation duration s t

k will be constructed.First a shortest path tree rooted at the sink with weight function w P e~C Tis built (line 6).Then we use the concept

of greedy algorithm for weighted set multi-cover problem

to select the source set (lines 7–10).The weighted set multi-cover problem is an extension to the weighted set cover problem by requiring that each element is covered by multiple times.Considering P i as the subset and w i SPT e~C Tas the subset weight in weighted set multi-cover problem,denoting P tk i as the set of targets that have not been K -covered in P i ,we greedily select the sensor that

has the minimum value of

P m 2P i

r m w i SPT e~C T

j P tk

j as the source node

until all the targets are covered K times.The shortest path from each selected source node to the sink builds the observation assignment (line 11).The duration of the phase ends when the duration of the iteration ends or any node s i consumes E 0es i T=k units of energy in the phase (line 12).The value of c i will be updated according to the amount of energy that node s i has consumed in duration

s t k ,which is denoted as e tk

i (line 13).The duration of each iteration s p will be doubled every 2k iterations (line 16).We present the method to scale the problem (line 1),analyze the approximation ratio and discuss the value of k ,d in the next Section (Section 5.4).Then we explain why s p is doubled (line 16)and analyze the complexity in Section 5.5.5.4.Analysis

We ?rst explain the scaling method used in our algo-rithm so that b P 1.Let T 1denote the lifetime achieved by solving the corresponding LMOS-1problem.From claim 1,we have T 1=M 6b 6T 1.Thus scaling the initial energy of each node by T 1=M or increasing each r m by a factor T 1=M can guarantee that M P b P 1.With b P 1,we car-ry out the analysis as given below.

Let K t denote the number of phases in iteration t ,~C et ;k Tdenote the vector of c i after the k th phase of iteration t .Assuming that the q th source set in U is selected as the source set in the k th phase of iteration t ,Using the de?ni-tion of path weight w P e~C T,the value of D e~C Tat the end of this phase is

Table 2

Pseudo-code for the approximation algorithm (01)Scale the problem so that b P 1;

(02)t ?0;L f ?0;d ?N

1à H e

b M T à1=

;8s i 2S ,set c i ?d =E 0es i T;k ?log 1=d 1t ;s p ?1=k ;

(03)while D e~C T<1;(04)s t

?0,k ?0;(05)while s t

~~(06)k ?k t1;Build the shortest path tree with the path weight w P e~C T;S t k ?/;for 8s i 2S ,P tk~~

~~i ?P i ;~~

~~(07)while exists target not covered K times by S t~~

~~k ;~~

~~(08)select s i 2S t k with the minimum P m 2P~~

~~r m w i SPT e~~~

~~C T~~

~~j P tk~~

~~i j ;(09)Add s i into S t k ;Update P tk~~

~~j ;(10)Endwhile ;~~

~~(11)The shortest path from each sensor in S t k to the sink constructs the observation assignment /t~~

~~k ;~~

~~(12)The operation duration s t k of /t k ends when s t k ?s p às t~~

~~or any node s i in /t k consumes E 0es i T=k unit of energy;~~

~~(13)s t ?s t ts t k ;c i et ;k T?c i et ;k à1T?e1t ák e tk~~

~~E 0es i TT,where e tk i is the energy consumed by s i in duration s t k .(14)Endwhile ;~~

~~(15)t ?t t1;c i et ;0T?c i et à1;k T;if D e~C T<1,L f ?L f ts p .(16)double s p every 2k iterations.(17)~~

~~Endwhile ;~~

~~Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–22202213~~

~~D e~C et ;k TT?~~

~~X i~~

~~ec i et ;k à1TTE 0es i T1t~~

~~k e tk i~~

~~E 0es i T e32T~~

~~?D e~C et ;k à1TTt s t k k~~

~~?X i~~

~~X iq X m 2P i~~

~~r m w i SPT e~C et ;k à1TT:~~

~~e33T~~

~~Recall the de?nition of a e~C T,as greedy algorithm is a H ek Tapproximation algorithm for weighted set multi-cover~~

~~problem,where H ek T?P~~

~~16i 6k 1i and k is the maximum sub-set size,we have~~

~~X iq X m 2P i~~

~~r m w i SPT e~C et ;k à1TT6H eb M Ta e~C et ;k à1TT;e34T~~

~~where b M~~

~~is the maximum number of targets in the sensing area of any sensor.As the algorithm proceeds,the link weights are monotonically non-decreasing.Therefore~~

~~a e~C et ;k à1TT6a e~C et ;k TT:~~

~~e35T~~

~~For any iteration t P 1,using Eqs.(33)–(35),~~

~~D e~C et ;0TT6D e~C et à1;0TTt k X~~

~~16k 6K t à1~~

~~s t à1k~~

~~áH eb M Ta e~C et ;0TT:e36T~~

~~If s p is never doubled,P~~

~~16k 6K t à1s t à1~~

~~?s p ?1=k .We assume that s p is never doubled now and will explain latter why the approximation ratio still holds when this assumption is removed in Section 5.5.From Eq.(36)~~

~~D e~C et ;0TT6D e~C et à1;0TTt H eb M Ta e~C et ;0TT:~~

~~e37T~~

~~The following analysis proceeds as Garg–Konemann algo-rithm [32]by replacing by H eM T .Let T denote the itera-tion that the algorithm ends,i.e.D e~C eT ;0TTP 1.As Eq.(3)~~

~~in [32],we have b~~

~~T à1~~

~~6 H eb M~~

~~Te1à H eb M TTln e1à H eb M TN d~~

~~e38T~~

~~In each iteration,the network lifetime will be increased by~~

a duration of 1=k .Since the algorithm ends when D e~C eT ;0TTP 1,the network lifetime is L ?eT à1T=k .Lemma 2.The solution of our approximation algorithm is a feasible solution for the LMOS-2problem,eT à1T=k is strictly less than the optimal solution of the LMOS-2problem.

Proof.Consider an arbitrary node s i 2S .In any phase k of any iteration t ,the energy consumption of s i will be less than equal to E 0es i T=k .Thus for every E 0es i T=k units of energy consumed by node s i ,the value of c i will be increased by at least a factor e1t T.

~~Initially,c i equals to d =E 0es i T.In the iteration before the~~

~~algorithm ends,as D e~C eT à1;0TT?P~~

~~i c i eT à1;0TE 0es i T<1,we have c i eT à1;0T<1=E 0es i Tfor any node s i .Therefore,the total amount of energy consumption of node s i is~~

~~strictly less than log 1t 1=E 0es i T~~

~~0i ?E 0es i T=k ?E 0es i T.Hence~~

~~proved.h~~

~~Theorem 4.Our algorithm is a H eb M~~

~~Te1tw Tapproximation for the LMOS-2problem.~~

~~Proof.Let c denote the approximation https://www.wendangku.net/doc/7c14589949.html,ing Eq.(38)~~

~~and from Lemma 2,reminding d ?N~~

~~1à H eb M~~

~~T à1=~~

~~,in the way~~

~~similar to [32],we have c <~~

~~b 6H eb M Te1à H eb M TTà1e1à Tà2e39T?H eb M~~

~~Te1tw Te40T~~

~~Hence proved.h https://www.wendangku.net/doc/7c14589949.html,plexity analysis From Lemma 2,16c <~~

~~eT à1T=k~~

)

~~T <1tbk :~~

~~e41T~~

~~Therefore,the total number of iterations T until the~~

approximation algorithm terminates is strictly less than 1tbk .In fact,if our algorithm does not terminate after 2d k e ,we know b P 2and can double the duration of itera-tions s p .Note that this is equivalent to re-scaling the prob-lem.b will be half of its previous value but still larger than 1,and thus the approximation ratio still holds.As we re-peat this procedure until the algorithm terminates,the approximation algorithm will terminate in 2d k e log 2M iter-ations (b 6M after scaling).

We note that in each phase of an iteration,except for the last phase,there exists at least one node s i that con-sumes energy E 0es i T=k ,whose c i is increased by a factor 1t .Since for any node s i ,the initial value of c i is d =E 0es i Tand the ?nal value is less than 1=E 0es i T(for D e~C T<1),the number of phases exceeds the number of iterations by at most N log 1t 1?N k (otherwise there exists at least one sensor s i whose c i exceeds 1=E 0es i T).In each phase we build a shortest path tree and greedily select the source nodes until all the targets are covered,which requires O eN 2Tand O eN min eM ;N TTtime,respectively.Therefore,the time complexity of our algorithm is e2log 2eM TtN Td 1 log 1t eN 1àH eb M T Te O eN 2tN min eM ;N https://www.wendangku.net/doc/7c14589949.html,munication weighted observation scheduling algorithm 6.1.Motivation

Although in Section 4an optimal solution of LMOS-1problem has been developed,the solution is an off-line centralized algorithm.Any initial input variations due to sensor nodes failures,new nodes deployment or sensor movements,will make the computed schedule unusable and force the algorithm to be re-executed.As solving the LP problem is computationally complex and sensors are as-sumed unreliable low price devices,the implementation cost of the optimal solution in the unreliable sensor net-work may be high.The approximation algorithm in Section 5provides useful theoretical insights into the LMOS-2problem and is more ?exible for input variations as it gen-erates observation assignments one by one based on the current network status.On the other hand,the number

~~2214Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–2220~~

~~of observation assignments generated could be large,be-~~

cause,to achieve satisfactory results,we need to set to be small,which results in a small d and large k.As generat-ing a new observation assignment will incur protocol cost, e.g.exchanging node status among neighbors and broad-casting the operational duration of the observation assign-ment,the protocol cost of the approximation algorithm will be high.Therefore,it becomes necessary to develop a ?exible low-cost heuristic protocol for the LMOS problem for both scenarios,which can be implemented in the real applications.

~~6.2.Algorithm description~~

The heuristic algorithm generates the observation assignments one by one based on the current network status.It uses a greedy method to construct the observa-tion assignments to cover the targets and it couples the communication cost and source set selection.Hence it is called Communication Weighted Observation Scheduling (CWOS).The inputs of the algorithm include graph G?f V;E g and initial energy E0es iTof each sensor s i.The output of the algorithm is a sequence of observation assignments/e1T;/e2T;...;/eXTand their operation dura-tions s/e1T;s/e2T;ááá;s/eXT.

The pseudo-code for the algorithm is shown in Table3. The algorithm repeatedly constructs feasible observation assignments and stops until no new observation assign-ment can be built(i.e.,the network lifetime is reached). Each observation assignment operates for a?xed time duration s p,unless any sensor selected by the observation assignment dies due to the lack of energy.Let E r

~~denote~~

~~the residual energy of s i and e/~~

~~denote the energy con-sumption rate of node s i given the observation assignment /.Thus,the operation duration of a feasible observation~~

~~assignment/is given by s/?mines p;min s~~

~~eE r~~

~~=e/~~

~~TT.~~

In each iteration,there are two steps to build the obser-vation assignment.In the?rst step,an energy-aware com-munication tree is constructed connecting all the live sensor nodes to the sink.In the second step,the source sensors which observe targets are selected,and the paths from these sources to the sink construct the observation assignment.

~~In the?rst step,a weight w ij is assigned to each link between live sensors s i and s j which re?ects both the com-munication energy consumption on the link and the resid-~~

~~ual energy level of the sender.Here we use w ij?e t~~

~~E0es iT=E r~~

.A minimum weight communication tree(MWCT) TexTis then constructed connecting all sensors such that the sum of the link weights from each node to the sink is minimized.For each live sensor s i on TexT,it remembers the sum of link weights from itself to the sink through TexT,which is denoted by W i.

In the second step,a modi?ed greedy set cover algo-rithm is developed to select the source set that covers each target at least K times.The algorithm greedily selects the sources among the live sensors which have not been se-lected and has at least one target not K-covered in its sens-ing area.For different observation scenarios,the procedure is a little different:

~~For LMOS-1problem,the sensor with the minimum path weight to the sink(W i)is selected as the source.~~

The new source randomly chooses target not K covered in its sensing range to observe until L targets or all the targets not K covered in its sensing range are observed by it.Then the next new source is selected.

~~Table3~~

~~Pseudo-codes for the heuristic algorithm~~

~~Input:G?f V;E g~~

~~Output:f/e1T;/e2T;ááá;/eXTg,f s/e1T;s/e2T;ááá;s/eXTg.~~

~~(01)T?0,x?1;~~

~~(02)while(1)~~

~~step1:~~

~~(03)Each node s i assigns weight w ij?e t~~

~~ij ?E0es iT=E r~~

~~to any linkes i;s jT2E originating from s i;~~

~~(04)Build the minimum weight communication tree TexTrooted at sink R with link weight w ij;~~

~~step2:~~

~~(05)Call modi?ed greedy set-cover algorithm to?nd set of sources;If return FALSE,break;~~

~~(06)The route from each source to the sink via MWCT constructs the observation assignment/exT;~~

~~(07)Each node s i estimates its energy consumption rate e/~~

;

~~(08)s/exT?mines p;min ieE r~~

~~i =e/~~

~~TT;~~

~~(09)x?xt1,T?Tts/exT;Update the network,delete dead or isolated nodes;~~

~~(10)Endwhile~~

~~Modi?ed Greedy set-cover algorithm~~

~~(01)P??P;let S?denote the set of unselected sensors cover at least one target in P?;~~

~~(02)While S??/and P??/~~

~~(03)If LMOS-1,~~

~~(04)Select s i2S?with minimum W i into source set;~~

~~(05)If j P?\P i j>L,randomly select L targets from P?\P i to be observed by s i;~~

~~(06)Else all the targets in P?\P i are observed by s i;~~

~~(07)If LMOS-2,~~

~~(08)Select s i2S?with minimum C i into source set;~~

~~(09)Delete targets covered at least K times from P?;~~

~~(10)Update S?,update c i for each sensor s i2S?;~~

~~(11)If the source set cannot cover all the targets K times,return FALSE;~~

~~(12)Else return the source set;~~

~~Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–22202215~~

~~For LMOS-2problem,for each sensor s i ,a cost function is~~

~~de?ned as C i ?W i P~~

p m 2P i r m =j P ?i j ,where P i is the set of targets in the sensing range of s i and P ?i is the set of tar-gets without K covered in the sensing area of s i .The sen-sor with the minimum cost function is selected as the new source node and the cost function of other sensors are updated accordingly.The procedure of selection ends until no more source nodes can be selected.In practice,this algorithm can be implemented in a distributed way as following.For each node s i ,we de?ne set S n ei Twhich contains non-source sen-sors that cover at least one target without K -covered which is also in the sensing area of node s i .If s i has the minimum value of weight/cost in S n ei T,s i must be selected before other sensors in S n ei T.Therefore,let each sensor s i broadcasts its weight/cost value to all the nodes in S n ei T,if a sensor s i ?nds its weight/cost value to be the mini-mum one in S n ei T,it claims itself as the source node,se-lects targets to observe (for LMOS-1problem)and broadcasts message to all other nodes in S n ei Tto update their information.The procedure continues until s i is se-lected as the source or all the targets in the sensing area of s i are K covered.

Finally,each source node sends a message through T ex Tto the sink notifying the bypassing relay nodes (line 6).Each active node sums the amount of data to be sent and estimates the amount of energy consumption in the next operation duration (line 7).If any sensor forecasts that it will consume more energy than its residual en-ergy,it will calculate the operation duration and broad-cast it to all the other sensors.A sensor will wait for a period of time (suf?cient to complete the building of observation assignment)after the source selection proce-dure to determine the length of the next operation dura-tion.Then it goes into sleep until the end of the operation duration.

For LMOS-1problem,let T denote the optimal lifetime archived by solving LP problem in Section 4.1;for LMOS-2problem,let T denote the lifetime upper bound in claim 1.Each observation assignment operates for a duration s p otherwise at least one sensor will die.Therefore,the num-ber of observation assignments to be built in the heuristic algorithm is upper bounded by N tT =s p .In each iteration,the complexity of constructing MWCT is O eN j E jTusing Bell-man-Ford algorithm,the complexity of source selection procedure is O eKMN T,and thus the complexity of CWOS algorithm is O eeKMN tN j E jTeN tT =s p TT.

Note that the modi?ed greedy set cover algorithm (step 2)for LMOS-1problem does not necessarily generate a feasible source set when there still exists feasible source sets.To study whether the performance of CWOS algo-rithm can be further improved by using other algorithms to select the source set,we develop another more complex algorithm to select the source set for LMOS-1problem.Consider the graph constructed by the observation links together with the sensors and targets connected with the observation links.Set the link capacity and link cost of each observation link ep m ;s i Tto be 1and r m W i .By adding a source node s connecting all the targets with link capac-ity K and link cost 0,and a destination node t connecting

all the sensors with link capacity L and link cost 0,the problem of ?nding a feasible source set can be converted to a minimum cost maximum ?ow problem on the graph.A modi?ed Edmonds–Karp (E–K)algorithm [14,p.660]can be developed to solve the minimum cost maximum ?ow problem and hence ?nd a feasible source set with the minimum total path weight.The E–K algorithm has been shown to ?nd a feasible source set if exits.It repeat-edly ?nds the minimum cost path from s to t on the resid-ual network and admitting ?ow on the path.Let us call the modi?ed CWOS algorithm which selects source set using the modi?ed E–K algorithm as CWOS-EK.We will compare the performance of the two algorithms (CWOS and CWOS-EK)and show that they can achieve almost the same per-formance in Section 7.

~~7.Performance study~~

In this section we present the numerical results and evaluate the performance of the approximation algorithm and heuristic algorithm we have proposed.CPLEX is used to solve the LP problem formulated for LMOS-1.The per-formance of the heuristic algorithm is evaluated in terms of network lifetime T and the number of observation assignments.

We consider the stationary networks with sensor nodes and targets uniformly located in a square of 100m ?100m area.The sink node is placed in the middle of the area.The communication range of each node R c ?40m.The va-lue of various parameters are chosen to be e t ?50nJ =bit,

~~b ?100pJ =bit =m 4~~

,a ?4,e r ?150nJ =bit and e s ?150nJ =bit [28].We assume that each target produces data at the same rate 10kbps,and each sensor has the same initial energy 20J.Each value plotted on the ?gure or shown in the table is the average result of 100randomly generated topologies.7.1.LMOS-1

In Fig.2we study the impact of L –the number of tar-gets a sensor can simultaneously observe –on the net-work lifetime with different values of K ,N and M .The sensing range R s ?40m.The value of each point is nor-malized by the network lifetime achieved corresponding to L ?1.It can be observed that the network lifetime is improved as L becomes larger.When the number of tar-gets is larger or the coverage requirement is higher,the improvement of lifetime with the increasing L is more signi?cant.

In Fig.3we compare the network lifetime achieved by CWOS algorithm with the optimal lifetime when the net-work density increases for different values of K and L .The sensing range R s ?40m.The number of targets in the network is ?xed at 20.The number of nodes is in-creased from 50to 130,thus the density is varied.As the network lifetime may vary greatly for different topology,the value of s p is set to be L LP =2M ,where L LP denotes the network lifetime in the optimal solution.It can be observed that the network lifetime increases nearly linearly as the number of nodes increases.The CWOS algorithm can

~~2216Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–2220~~

~~achieve at least 90%of the optimal network lifetime in all the cases.~~

In Table 4we compare the network lifetime achieved by CWOS algorithm with CWOS-EK algorithm for different values of N and L .The sensing range R s is set to be 40m ,the number of targets is set as 20and K is set as 1.It can be observed that CWOS algorithm achieves almost the same lifetime as CWOS-EK.

~~Table 4~~

~~Comparison of CWOS with CWOS-EK algorithm for LMOS-1problem (N ,L )~~

~~Lifetime (s)Optimal~~

~~CWOS-EK CWOS (60,1)253.717242.352236.749(60,10)387.576369.199364.739(100,1)675.518629.674627.944(100,10)~~

~~955.277~~

~~887.049~~

~~885.589~~

~~Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–22202217~~

~~7.2.LMOS-2~~

As the connectivity issue is not considered in most existing works on discrete target problem,we compare the performance of our algorithms with the greedy_MSC algorithm proposed in[8]with suitable modi?cation to ac-count for the connectivity.This modi?cation is done by using an energy-aware communication tree which is built in a similar way as our CWOS algorithm to transmit the sensed data to the sink node.We refer the modi?ed algo-rithm as GrMSC_EW.The greedy_MSC algorithm greedily selects a‘‘critical”target and then selects the sensor with the greatest contribution to the‘‘critical”target until all the targets are covered.The‘‘critical”target is chosen as the target in the sensing area of the least number of sen-sors,and the contribution function is chosen as the number of uncovered targets in the sensing area of a sensor.

In Table5,the network lifetime(lifetime)achieved and the number of observation assignments(Num.Ass.)gener-ated by CWOS algorithm,the approximation algorithm and GrMSC_EW algorithm are compared when the network parameters K,N and M are taken different values.The sens-ing range R s?20m.For CWOS and GrMSC_EW algorithm, the value of s p is set to be L LP=2M,which implies that the number of observation assignments are bounded by 2MtN.For approximation algorithm,the value of is set to be0.1.It can be observed that in all the cases CWOS algorithm can achieve similar(within5%lower)network lifetime as the approximation algorithm while generating much less observation assignments.The CWOS algorithm can achieve signi?cantly(as24%)higher network lifetime than GrMSC_EW algorithm.As expected,for all the algo-rithms the network lifetime will increase as the number of nodes N increases,the number of targets M decreases or the coverage requirement K decreases.The number of observation assignments generated by the CWOS and GrMSC_EW algorithms increases as the number of nodes or the number of targets increases.This is due to the in-creased upper bound of number of observation assign-ments2MtN.

The construction of new observation assignments in-curs protocol cost.To construct an observation assignment, any algorithm(CWOS,approximation or GrMSC_EW) needs to construct a communication tree and then select the source nodes to cover all the targets.Therefore,the number of observation assignments generated by the algo-rithms could be a good indicator for the potential protocol cost.As we have discussed above,CWOS algorithm can achieve similar lifetime with a much lower protocol cost compared with the approximation algorithm.We note that the construction of new observation assignments in CWOS and GrMSC_EW algorithms is time-based and related to the chosen value of s p.If both the CWOS and GrMSC_EW algorithms choose the same value of s p in the simulation, as CWOS algorithm can achieve higher network lifetime, CWOS will generate more observation assignments.We set K?1,N?100,M?20and R s?20m.For s p?L LP=2M,the mean number of observation assignments gen-erated by CWOS and GrMSC_EW algorithms is55.6and 42.7,respectively.The lifetime generated by the two algo-rithms is408.23and331.09,respectively.However,when s p is increased to L LP=M,the network lifetime of CWOS algorithm slightly decreases to405.42which is still much higher than the lifetime of GrMSC_EW algorithm when s p?L LP=2M,while the number of observation assignments of CWOS algorithm drastically decreases to43.9which is similar to that of GrMSC_EW algorithm when s p?L LP=2M.Therefore,by suitably selecting the value of s p, CWOS algorithm can incur a protocol cost close to that of GrMSC_EW while achieving signi?cantly better perfor-mance in terms of lifetime.

~~7.3.Discussion~~

We note that the values for battery energy and source data rate used in the simulation are for the purpose of comparing the performance of the algorithms and studying the impact of network parameters on the algorithm perfor-mance.In fact,the lifetime can be proportionally increased (decreased)by increasing(decreasing)the initial energy of each node or decreasing(increasing)the data rate out of each source sensor.For example,in Fig.3,the maximum value of network lifetime achieved is about1200s for an initial battery energy of20J.However,in practice the ini-tial energy of a sensor node could be of the order of KJ. For example,a Mica2node[33]uses2AA batteries.A typ-ical AA alkaline battery can discharge about100mw power for about20h,which implies an approximate initial en-ergy of7KJ per battery.For the initial energy of10KJ and source data rate of10kbps,the network lifetime achieved would be about166.7h;and for the source data rate of1Kbps,each target can be continuously monitored for about1667h.

The energy consumption for network formation is not considered in the simulation experiments presented ear-lier.Given the network formation algorithm and the initial network topology,for each node,the energy consumption for network formation would be a relatively?xed value. Thus the impact of network formation on the network life-time can be eliminated by adjusting the corresponding en-ergy consumption from the initial energy of each sensor node.As network formation algorithm may produce un-even distribution of energy consumption of sensors,we as-sume that the initial energy of each sensor node is not identical.We also carry out the simulations as in Sections 7.1and7.2but setting the initial energy of each node to be randomly distributed among10–30J.Similar results are achieved compared with the situation when the initial

~~Table5~~

~~Comparison of CWOS with approximation and GrMSC_EW algorithm for LMOS-2problem~~

~~(K,N,M)CWOS Approximation GrMSC_EW~~

~~Lifetime Num.~~

~~Ass.Lifetime~~

~~(s)~~

~~Num.~~

~~Ass.~~

~~Lifetime~~

~~(s)~~

~~Num.~~

~~Ass.~~

~~(1,60,15)152.7026.40156.302368.8129.2521.90~~

~~(1,100,15)492.4742516.175069.2426.3336.2~~

~~(1,130,15)898.971.6938.588138.4723.7458.5~~

~~(1,100,30)238.064.0239.364238.3196.052.4~~

~~(2,100,15)235.5142.3247.064983.4194.633.0~~

~~2218Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–2220~~

~~energy of each node is identical.Due to space limitation, only representative results are shown in Table6which could be compared with the results shown in Tables4and5. 8.Conclusions~~

In this paper,we have considered the Lifetime Maximi-zation Observation Schedule(LMOS)problem.Considering K-coverage of targets and connectivity as the application requirements and taking into consideration both the ob-served data and relayed data,we determine the schedule of observation time for each sensor to maximize the network lifetime.We have considered two observation scenarios in this paper.We have developed an optimal solution based on LP formulation and Integer theorem for the LMOS problem for the?rst scenario.As the LMOS prob-lem for the second scenario is NP-complete,we have devel-oped an ef?cient approximation algorithm for solving it.A low-cost heuristic algorithm for both scenarios has been developed which is useful for practical implementation. The performance has been studied and several useful observations have been made from numerical results ob-tained from CPLEX and extensive simulation results. References

~~[1]I.Akyildiz,W.Su,Y.Sankarasubramaniam,E.Cayirci,Wireless sensor~~

~~networks:a survey,Computer Networks39(4)(2002)393–422. [2]M.Cardei,J.Wu,Coverage problems in wireless ad hoc sensor~~

~~networks,in:Mohammad Ilyas,Imad Mahgoub(Eds.),Handbook of Sensor Networks,CRC Press,2004(Chapter19).~~

~~[3]C.-F.Huang,Y.-C.Tseng,A survey of solutions to the coverage~~

~~problems in wireless sensor networks,Journal of Internet Technology6(1)(2005)1–8.~~

~~[4]D.L.Hall,J.Llinas,Handbook of Multisensor Data Fusion,CRC Press,~~

~~2001.~~

~~[5]A.Arora,P.Dutta,S.Bapat,V.Kulathumani,H.Zhang,V.Naik,V.~~

~~Mittal,H.Cao,M.Demirbas,M.Gouda,Y.Choi,et al,A line in the sand:a wireless sensor network for target detection,classi?cation, and tracking,Computer Networks46(5)(2004)605–634.~~

~~[6]S.Slijepcevic,M.Potkonjak,Power ef?cient organization of wireless~~

~~sensor networks,in:IEEE International Conference on Communications(ICC),vol.2,June2001,pp.472–476.~~

~~[7]M.Cardei, D.-Z.Du,Improving wireless sensor network lifetime~~

~~through power aware organization,Wireless Networks11(3)(2005) 333–340.~~

~~[8]M.Cardei,M.T.Thai,Y.Li,W.Wu,Energy-ef?cient target coverage in~~

~~wireless sensor networks,IEEE INFOCOM,2005,pp.1976–1984.~~

~~[9]M.Cardei,J.Wu,M.Lu,M.O.Pervaiz,Maximum network lifetime in~~

~~wireless sensor networks with adjustable sensing ranges,in:IEEE International Conference on Wireless and Mobile Computing, Networking and Communications(WiMob),2005.~~

~~[10]M.Lu,J.Wu,M.Cardei,M.Li,Energy-ef?cient connected coverage of~~

~~discrete targets in wireless sensor networks,in:International Conference on Computer Networks and Mobile Computing (ICCNMC),2005.~~

~~[11]H.Liu,P.Wan,C.-W.Yi,X.Jia,S.Makki,P.Niki,Maximal lifetime~~

~~scheduling in sensor surveillance networks,in:INFOCOM,2005,vol.~~

~~4,pp.2482–2491.~~

~~[12]H.Liu,P.Wan,X.Jia,Maximal lifetime scheduling for k to1sensor-~~

~~target surveillance networks,Computer Networks50(15)(2006) 2839–2854.~~

~~[13]X.Wang,G.Xing,Y.Zhang,C.Lu,R.Pless,C.Gill,Integrated coverage~~

~~and connectivity con?guration in wireless sensor networks,ACM International Conference on Embedded Networked Sensor Systems (SenSys),2003,pp.28–39.~~

~~[14]T.H.Cormen, C.E.Leiserson,R.L.Rivest, C.Stein,Introduction to~~

~~Algorithms,second ed.,The MIT Press,McGraw-Hill.~~

~~[15]M.Cardei,J.Wu,Energy-ef?cient coverage problems in wireless ad-~~

~~hoc sensor networks,Computer Communications29(4)(2006)413–420.~~

~~[16]S.Meguerdichian, F.Koushanfar,M.Potkonjak,M.Srivastava,~~

~~Coverage problems in wireless ad-hoc sensor networks,in: INFOCOM,2001.~~

~~[17]S.Meguerdichian,F.Koushanfar,G.Qu,M.Potkonjak,Exposure in~~

~~wireless ad hoc sensor networks,in:MOBICOM,2001.~~

~~[18]H.Zhang,J.C.Hou,Maintaining sensing coverage and connectivity in~~

~~large sensor networks,Tech.Rep.,Department of Computer Science, University of Illinois at Urbana-Champaign,2003.~~

~~[19]P.Berman,G.Calinescu, C.Shah, A.Zelikovsky,Power ef?cient~~

~~monitoring management in sensor networks,in:WCNC,2004. [20]M.Cardei,D.MacCallum,X.Cheng,M.Min,X.Jia,D.Li,D.-Z.Du,~~

~~Wireless sensor networks with energy ef?cient organization,Journal of Interconnection Networks3(3)(2002)213–229.~~

~~[21]Z.Zhou,S.Das,H.Gupta,Connected k-coverage problem in~~

~~sensor networks,in:Thirteenth International Conference on Computer Communications and Networks(ICCCN),2004,pp.~~

~~373–378.~~

~~[22]D.Tian,N.D.Georganas,A coverage preserving node scheduling~~

~~scheme for large wireless sensor networks,in:Proceeding of the1st ACM Workshop on Wireless Sensor Networks and Applications, 2002.~~

~~[23]H.Gupta,Z.Zhou,S.R.Das,Q.Gu,Connected sensor cover:Self-~~

~~organization of sensor networks for ef?cient query execution, Networking,IEEE/ACM Transactions on Networking14(1)(2006) 55–67.~~

~~[24]Y.Liu,W.Liang,Approximate coverage in wireless sensor networks,~~

~~in:Proceedings of the IEEE Conference on Local Computer Networks 30th Anniversary(LCN’05),2005.~~

~~[25]L.Wang,S.S.Kulkarni,pcover:partial coverage for long-lived~~

~~surveillance sensor networks,Tech.Rep.MSC-CSE-0530, Department of Computer Science and Engineering,Michigan State University,2005.~~

~~[26]Z.Abrams,A.Goel,S.Plotkin,Set k-cover algorithms for energy~~

~~ef?cient monitoring in wireless sensor networks,in:IPSN,Berkeley, California,USA,2004.~~

~~[27]Q.Zhao,M.Gurusamy,Lifetime maximization using observation~~

~~time scheduling in multi-hop sensor networks,in:IEEE/CreateNetw International Workshop on Broadband Advanced Sensor Networks (BroadNets),2005.~~

~~[28]J.-H.Chang,L.Tassiulas,Maximum lifetime routing in wireless~~

~~sensor networks,IEEE/ACM Transactions on Networking12(4) (2004)609–619.~~

~~[29]M.Bhardwaj and A.P.Chandrakasan,‘‘Bounding the lifetime of~~

~~sensor networks via optimal role assignments,”in:INFOCOM,vol.3, 2002,pp.1587–1596.~~

~~[30]K.Kalpakis,K.Dasgupta,P.Namjoshi,Maximum lifetime data~~

~~gathering and aggregation in wireless sensor networks,Tech.Rep., Computer Science and Electrical Engineering Department,University of Maryland Baltimore County,2002.~~

~~[31]N.Sadagopan, B.Krishnamachari,Maximizing data extraction in~~

~~energy-limited sensor networks,in:INFOCOM,vol.3,2004,pp.~~

~~1717–1727.~~

~~[32]N.Garg,J.Konemann,Faster and simpler algorithm for~~

~~multicommodity?ow and other fractional packing problems,in: FOCS,1998.~~

~~[33]Mica2Datasheet..~~

~~Table6~~

~~Network lifetime achieved with non-identical initial energy values~~

~~LMOS-1~~

~~(N,L)Lifetime(s)~~

~~Optimal CWOS-EK CWOS~~

~~(60,1)248.6236.6230.8~~

~~(60,10)396.24376.4376.4~~

~~(100,1)658.9613.34610.9~~

~~LMOS-2~~

~~(K,N,M)Lifetime(s)~~

~~CWOS Approximation GrMSC_EW~~

~~(1,60,15)147.6153.84125.2~~

~~(1,100,15)478.137493.634393.762~~

~~(1,100,30)216.97221.92183.2~~

~~Q.Zhao,M.Gurusamy/Computer Networks52(2008)2205–22202219~~

Zhao Qun received the B.S.and M.S.degrees in Electronic Engineering from Tsinghua University,Beijing,China,in 2000and 2003.He is currently pursuing the Ph.D.degree in the Department of Electri-cal and Computer Engineering,National University of Singapore.His research interests include Wireless Sensor Net-works.He is a student member of the

~~IEEE.~~

Mohan Gurusamy received the Ph.D.degree in Computer Science and Engineer-ing from the Indian Institute of Technology,Madras in 2000.He joined the National University of Singapore in June 2000,where he is currently an Assistant Profes-sor in the Department of Electrical and Computer Engineering.He has held a vis-iting position at Iowa State University,USA,from January to June 1999.He served as the lead guest editor for two special issues on Optical Networking Testbeds of the IEEE Communications Magazine (OCS),August

~~2005and November 2005.He was the organizer and lead chair of IEEE/~~

CreateNet GOSP workshop colocated with IEEE/CreateNet Broadnets conference,October 2005and October 2006,USA.His research interests are in the areas of high speed multi-wavelength optical circuit and burst switching networks,wireless sensor networks,and grid networks.He has over 100research publications to his credit and co-authored two books in the area of optical networks.He has been a member of the IEEE since 2000and senior membner since 2007.

~~2220Q.Zhao,M.Gurusamy /Computer Networks 52(2008)2205–2220~~

敬语

敬语基础语言是人类交往沟通的主要工具，为了达到正确顺利地交往沟通的目的，“谈话得体”是最首要的条件。而所谓谈话得体，指的是在适当的场合使用适当的话语，对特定的对象采取特定的交谈方式。日语中的敬语在这方面要求特别严格。若在应该使用敬语的场合没有使用敬语，或用了错误的敬语，不但会给人留下不礼貌、不会处世的印象，甚至可能会因此而破坏了双方的关系。而在不应该或没必要使用敬语的场合使用了敬语，也会给人留下不好的印象。俗话说：“祸从口出”，敬语使用不当，常常会无意中就为自己闯下或大或小的祸，或惹出麻烦来。具体说来，日语里的敬语由尊敬语（尊敬語）、自谦语（謙遜語）、郑重语（丁寧語）（美化语）三大部分组成。所谓尊敬语是抬高对方（谈到的对象）或其动作和所有物（所属）的一种表现。如： “昨日、社長がおっしゃったことをよく考えてみました。” （表示提高对方的动作“言う／说”）（“我认真地考虑了昨天总经理所说的事情。”） “これは設計部の小林さんが提出された報告でしょうか。” （表示抬高所谈到的人“小林さん”的动作“提出する／提交”）（“这是设计部的小林先生提交来的报告吗？”）即使对方或所谈到的人年龄和职位都不比你高，也每每用尊敬语。尊敬语的用法 [动词] 与えるくださるたまわる言うおっしゃる行くいらっしゃるいるあるいらっしゃるおいでになる着る召す（めす）お召しになる来るいらっしゃるみえるおいでになるおこしになるするなさるあそばす寝るお寝み（やすみ）になる食べる召し上がる見る御覧になるお目にとめるお目にとまる聞くお耳にはいる命ずるおおせつける [接头词] おごおんみおみ例如：お志ご出発 [接尾词] 様さん殿君 [代词] あなたそちら自谦语是一种降低讲话人（或讲话方面的人）的动作、所有物（所属），以此来抬高对方的

敬语

四、常用敬语 A)日常敬语 1、営業部のどなたをお呼びしましょうか。 (误) 営業部のだれを呼びましょうか。(正) 在一家重视对职员进行礼貌教育的大企业里，如果其传达室的人员对来访者说：「どなたにご面会ですか」，人们听后，就该对这家公司职员教育的内容产生怀疑。打电话也一样，来电话说：「営業部をお願いします」(我找营业部)。如果你问道「営業部のどなたをお呼びしましょうか。」(您找营业部的哪一位？)，那么，这就出现了表达上的错误。因为你对自己公司的人用了敬称「どなた」。正确的说法是「だれを呼びましょうか」。当然，公寓、饮食店等，可另当别论。在这种场合招呼客人时，使用「どなたをお呼びしましょうか。」是正确的。 2、山田は，席をはずしております。 (误) 山田さんは，席をはずしております。(正) 对方打来电话询问“山田先生在吗？”如果你回答：「山田は，今，席をはずしております。」对方听后就会产生不快，原因就在于直呼其姓了。接电话时，直呼自家的丈夫、兄弟等人的姓，就如同无知、鄙俗、大喊大叫一样，当然会影响交际气氛，伤害对方的感情。接电话时，对自己这一方的人，也应该用诸如「課長さんは，外出しております」 (科长他外出了)的说法，这是原则。即使是对新职员也不能直呼其名，应在其后加「さん」。 B)社内敬语 1、部長，私の説明がわかりますか。 (误) 部長，私の説明がご理解いただけたでしょうか。(正) 使用上面的错误说法，会使局外人觉得：问题大概过难了吧！部长真笨，理解不了。年轻的职员如果在给部长的报告前面加上「おわかりになりますか」这样的话，部长会因此而恼怒。这是因为「わかる」这个词含有能力欠佳的意思。就是说「わかりますか」这句话是问对方有没有这个理解能力。并且，用在这里往往被认为这是在影射部长的能力低下。在这种情况下，通常要说「これでよろしいでしょうか」(这样，行不行？)或「部長，ご理解いただけたでしょうか」(部长，您理解了吧)。当然，在日常会话中可以用，但要分具体场合。「わかる」「できる」等都是表现“能力”与“可能”的词，对上级、老师、长辈等不宜使用。但目前在这方面不注意的人却很多。应该记住：对上级、老师、尊长等，要避免使用「わかる」「できる」这些词，否则会有目无尊长之嫌。 2、課長が「おまえから伝えよ」とおっしゃいました。 (误) 課長が「わたしからお伝えするように」とおっしゃいました。(正) 受科长之命，科员去向部长汇报时，有时会说出上面错误例句中的话。意思是，“科长说由我来汇报(所以我来了)”。部长若听到这样的话语，恐怕会感到不高兴。因为，这样的说法太直接了，也太生硬了。对于听话一方来说，「おまえ」「せよ」这类生硬的说法，是难以令人接受的粗鲁语言。这种直接引用原话的表达方式，往往容易招至误解。因此，要特别注意，以免引起听话一方的不快。碰上科员真被上司说成「君から」这样的事，通常不宜直接引用，因为「君から」用于指自己时，是不妥的，会引人发笑。谦逊地说成「おまえから」又有被误解的可能。用「わたしからお伝え申し上げるように」这样的说法最为合适，既能间接表达语意，也不会引起误解，对于类似部长的上司又不失礼。 3、部長，それでは，お教えします。(误) 部長，それでは，ご説明いたします。 (正) 如果部长对一个下属说：「ここがちょっとわからないので、教えてくれないか」，而下属则回答说：「はい、それではお教え申し上げます」。这样的回答是不妥的。部长听了一定会生气的。因为对上司，用「教える」这样的词语，会给听者一种“看不起自己”的感觉。即使用「お教え申しあげます」这一更自谦的说法，也是一样的。因为「教える」这个词含有自上而下“教”的这层意思，因此会令听者感到不高兴。这里应该用「ご説明(いた)します」为宜。 4、社長は，ゴルフをおやりになりますか。(误) 社長は，ゴルフをなさいますか。(正) 不少人常常使用「おやりになる」这句别扭的敬语。「社長は，奥様とゴルフをおやりになりますか。」「まあ、たまにだが」提问的一方，或许是为了对公司经理表示敬意，才这样讲的。可是殊不知「おやりになりますか」这句话，无论如何加「お」都构不成敬语。因为「やる」这个词，一直是用来表达自己行为时使用的。并且，使用「やる」也略微显得品格低下、人格卑微。「私は、ゴルフをやる」这样用于自身的说法，绝对没有什么错误。不过，在郑重的场合，说「ゴルフをする」更为合适，不会惹贵妇人们讨厌。对上级或长辈讲话时，要使用「する」的敬语「なさる」。前面那句话的正确说法应是：「社長は，ゴルフをなさいますか」(经理打高尔夫球吗？)

各种场合使用的日语敬语集锦

我最近正在看一本讲敬语的书，内容很不错，可惜不能都搬来，只能把例句抄下来，分析部分只好割爱了。書名：仕事に必要なのは英語の前に敬語でしょ一．尊敬語の正しい使い方 1. 職場の同僚を呼ぶとき ×山田君、コーヒーをお願いします〇山田さん、コーヒーをお願いしますポ?ント：「君」は名前のあとにつくと相手を低める呼び方になる 2. 目的の人物が在社かどうかをたずねるとき ×山田様はおられますか〇山田様はいらっしゃいますかポ?ント：「おる」は謙譲語。敬語の助動詞「れる」をつけても敬語にはなりません 3. 他社の社員を役職名で呼ぶとき ×おたく様の課長さんは… 〇おたく様の課長は… ポ?ント：「役職名＋さん」は二重敬語となり不適切 4. 講演会の講師の到着を上司に伝えるとき ×山田先生がまいっています〇山田先生がおいでになっていますポ?ント：敬意の度合いは、「いらっしゃる」→「おいでになる」→「お見えになる」→「お越しになる」の順に高くなる 5. 客に注文を聞くとき ×ご注文は何にいたしますか〇ご注文は何になさいますかポ?ント：「なさる」は言い方によってはきつく聞こえるので要注意 6. 話が聞き取れず、聞き返すとき ×何と申されましたか

〇何とおっしゃいましたかポ?ント：「おっしゃる」は意外に複雑 7. 上司に報告するとき ×すでに存じ上げていると思いますが〇すでにご存知のことと思いますがポ?ント：尊敬語と謙譲語の区別をつけよう 8. 会議の出席者に向かって ×お手元の資料を拝見してください〇お手元の資料をご覧くださいポ?ント：「拝見」は「拝み見る」という意味 9. 客に感想を聞くとき ×お気に入りましたでしょうか〇お気に召しましたでしょうかポ?ント：美しくて品のある「召す」の使い方を覚えよう 10. 「何を飲むか」と聞かれたとき ×おビールをいただけますか〇ビールをいただけますかポ?ント：外来語には「お」をつけない。「お」は和語に、「ご」は漢語につく 11. 食べ物や飲み物をすすめるとき ×冷めないうちにいただいてください〇冷めないうちに召し上がってくださいポ?ント：「いただく」は謙譲語、「召し上がる」「あがる」が尊敬語12. 上司に感謝の意を表すとき △課長からいただいた?ドバ?スのおかげで〇課長がくださった?ドバ?スのおかげでポ?ント：自分を低める謙譲語より、相手を高める尊敬語を使うほうが敬意の度合いは高い 13. 来客を告げるとき

何时用敬语办公室谈吐礼仪

何时用敬语办公室谈吐礼仪语言是双方信息沟通的桥梁，是双方思想感情交流的渠道。语言在人际交往中占领着最基本、最重要的位置。语言作为一种表达方式，能随着时刻、场合、对象的别同，而表达出各种各样的信息和丰富多彩的思想感情。语言表达出来。说话礼貌的关键在于尊重对方和自我谦让。要做到礼貌说话必须做到以下几点：一、使用敬语、谦语、雅语（一）敬语敬语，亦称“敬辞”，它与“谦语”相对，是表示恭敬礼貌的词语。除了礼貌上的必须之外，能多使用敬语，还可体现一具人的文化修养。１、敬语的运用场合第一，比较正规的社交场合。第二，与师长或身份、地位较高的人的交谈。第三，与人初次打交道或会见别太熟悉的人。第四，会议、谈判等公务场合等。２、常用敬语我们日常使用的“请”字，第二人称中的“您”字，代词“阁下”、“尊夫人”、“贵方”等，另外还有一些常用的词语用法，如初次见面称“久仰”，很久别见称“久违”，请人批判称“请教”，请人原谅称“包涵”，烦恼别人称“打搅”，托人办事称“拜托”，赞人见解称“高见”等等。（二）谦语谦语亦称“谦辞”，它是与“敬语”相对，是向人表示谦恭和自谦的一种词语。谦语最常用的用法是在别人面前谦称自己和自己的亲属。例如，称自己为“愚”、“家严、家慈、家兄、家嫂”等。自谦和敬人，是一具别可分割的统一体。虽然日常日子中谦语使用别多，但其精神无处别在。只要你在日常用语中表现出你的谦虚和恳切，人们自然会尊重你。（三）雅语雅语是指一些比较文雅的词语。雅语常常在一些正规的场合以及一些有长辈和女性在场的事情下，被用来替代那些比较随便，甚至粗俗的话语。多使用雅语，能体现出一具人的文化素质以及尊重他人的个人素养。在待人接物中，要是你正在款待客人，在端茶时，你应该说：“请用茶”。假如还用点心款待，能够用“请用一些茶点。”如果你先于别人结束用餐，你应该向其他人打招呼说：“请大伙儿慢用。”雅语的使用别是机械的、固定的。只要你的言谈举止彬彬有礼，人们就会对你的个人修养留下较深的印象。只要大伙儿注意使用雅语，必定会对形成文明、高尚的社会风气大有益处，并对我国整体民族素养的提高有所帮助。二、日常场合应对（一）与人保持适当距离说话通常是为了与别人沟通思想，要达到这一目的，首先固然必须注意说话的内容，其次也必须注意说话时声音的轻重，使对话者可以听知道。如此在说话时必须注意保持与对话者的距离。说话时与人保持适当距离也并非彻底出于思考对方能否听清自己的说话，另外还存在一具怎么样才更合乎礼貌的咨询题。从礼仪上说，说话时与对方离得过远，会使对话者误认为你别愿向他表示友好和亲近，这显然是失礼的。但是假如在较近的距离和人交谈，稍有

敬语使用

在日语中，敬语是非常重要的语素，跟什么人说什么话也可以说是日语的一大特点。学习敬语，首先要学会跟什么样的人使用敬语，我们先看一下敬语的使用方法 1 敬语的实用对象 A 对「目上」的人日语中有个非常形象的词，叫「目上」「目上の人」就是指的比自己地位高，需要尊敬的人。就好象你看他的时候，都要仰慕一样。对于老师、上司、长辈、和前辈（即使他年龄比你小），都要用敬语。例句的一般形式「山田先生は明日何じに来ますか。」「来る」「いる」的敬语形式都是「いらっしゃる」 B 对生人除了对「目上の人」使用敬语，对不熟识的人也用敬语。特别是在商店里，店员对客人是必须用敬语的。例句您叫什么名字。 C 当场合为郑重的场合时例句那么，诸位，现在开始开会。 2 敬语的类型在敬语中主要分为敬语和谦让语，叮咛语也被算在敬语中。要记住，分别是使用敬语还是谦让语的时候，主要看句子的主语。主语是需要尊敬的人，后面的动词等都要用敬语而当说话的对象是需要尊敬的人，主语是自己或自己的一派的时候，就要用谦让语。

叮咛语的用法是不分对象身份的高低的。一些单词的前面加上「お」，跟近似于一种习惯但是表达的形式是属于敬语的。 3 是「お」还是「ご」在日语的很多词前面都加「お」或「ご」来表示尊敬那么什么时候用「お」，什么时候用「ご」呢 A 「お」的后面，经常接「和语」所谓的和语，指的是「日制语言」，而不是原始的汉语比如，「花（はな）」，读法根汉语完全不同，就是和语在「花」的前面有时就接「お」 B 而「ご」则是接汉制日语的时候多比如「旅行」，「入学」等，前面就可以接「ご」但是，「汉语」的前面也有接「お」的时候一般的规律是「和语」前用「お」、「汉语」前用「ご」，但是遇到特殊的例子就要特殊记忆 1.敬語の使い方 A.上の人に対して使う「上の人」先生会社の上司年上の人など。例文山田先生は明日何時にいらっしゃいますか。 B.あまり親しくない人関係が近くない人に対して使う例文お名前はなんとおっしゃいますか。 C.あらたまったところで使う。

敬语具体的使用场合

敬語の具体的な使い方日语111班智硕园郑帅 (一)自分や相手の呼び方の問題自分 ?私（わたし）：虽说官方规定里是最正统的，其实日本人用的不多 ?私（わたくし）：わたし的敬语形式，不常用，一般有教养的女性多用。只有在极正式的场合男性才会使用 ?僕（ぼく）：年龄较小的男性多用，口语。 ?俺（おれ）：男性多用，比较粗犷，随便的说法，如果对长辈用此称呼，会显得很不礼貌 ?我（われ）：比较正式、书面的说法，男女通用，多用于演讲、开会、讨论严肃问题的时候相手 ?あなた：教科书所教的第一个指代“你”的词，表中立立场，一般不用于上级。另一个意思就是亲密的人之间的称呼妻子称呼丈夫也可用此称呼，通常译为“亲爱的” “老公” ?お前：最常用的比较随便的称呼，一般不对长辈使用，对平辈和晚辈可用，有时丈夫称呼妻子也用这个 ?君：比お前要随便一点，上级称呼下级可用 ?貴殿：（书信用语）您，通常为男性所用，用于对长辈或同辈的尊称（二）「ウチ?ソト」の關係における問題亲人向内称呼自己的亲人（尊称）語例称呼对方的亲人（尊称）向外称呼自己的亲人（谦称）夫ご主人、ご主人様夫、名前で呼ぶおとうさん、あなた、名前で呼ぶ妻奥様妻、女房、家内おかあさん、きみ名前で呼ぶ父母ご両親様、お父様、お母様両親、父母、父、母お父さん、お母さん儿子ご子息様、お坊ちゃま、息子さ息子、名前で呼ぶ名前で呼ぶん女儿お嬢様娘、名前で呼ぶ名前で呼ぶ

公司 ?向外称呼公司内部人员：对别公司的人说到自己公司的人时不要加上“さん”，而要直接叫姓名。不习惯这些规则的新人老是说不好总要加上“さん”。 ?在公司内部称呼别人：对于没有职称的前辈或同事说“○○さん”、上司，要叫职务名称为“○○部長”。对其他公司的人以及上级绝对不能叫“あなた”，而要礼貌的叫“○○様” （三）「ねぎらい」と「褒め」の問題ねぎらい对下班的人：上司お疲れ様でした同事、下属お先に、お疲れ様 ※「ご苦労さまでした。」这是上司慰劳部下的话，最好不要对上级使用。对给予帮助的人：どうもありがとうございました ※不要用「どうもご苦労様でした。」褒め褒められたら嬉しくなって、「もっと頑張ろう」とやる気が出てきます。そして、褒められる人だけではなく、褒める人の心も暖かくなります。ですから、日常生活の中で相手のいいところをよく見て、小さなことでも褒めるようにするとコミュニケーションがもっとうまくいくでしょう。ただし、あまり大げさな言葉で褒めてしまったり過剰な褒め方をすると逆効果になるので気をつけましょう。 ?赞扬别人：赞扬别人没问题，但是要注意，如果是别人应做的事，最好不要赞扬。 ?被赞扬：最好不回答「ありがとうございます」，应回答「とんでもない」的敬语形式「とんでもないでございます」。 ※「とんでもない」为形容词，不能将「とんでも」和「ない」分开，取「ない」得敬语形式「ございません」，所以「とんでもございません」为错误语法。（四）依頼の仕方の問題依頼は「すみません」「恐れ入りますが」などで始め、あくまでも謙虚にします。友人同士の場合でも、「ごめんね」「悪いんだけど」などと謙虚な姿勢を持つべきです。自分のしてほしいことばかり言うのではなく、相手の都合を考えることも大切です。たとえば、上司になにかを教えて欲しい時、「すみません、ご都合のよろしいときに教えていただきたいんですか、よろしいですか」などというと丁寧な依頼になります。また、相手がすごく忙しいそうなときは、タイミングを見て「ご都合の良いときに少しお時間いただけませんか」と聞きましょう。 ?この仕事をしていただけますか。 ?これお願いできますか。 ?お願いしてもいいですか。（五）「マニュアル敬語」の問題日本語の敬語には、尊敬語、謙譲語、丁寧語があります。尊敬語は話し相手や話題の人に対して、尊敬の気持ちを表す敬語です。話題の人や、そ

敬语用法归纳总结

日语复习资料之敬语用法归纳总结日语的敬语是学习日语的难点之一。由于内容比较复杂，所以很难掌握。学习了相当长时间日语的人，也容易说错。这里介绍最基本的部分，希望大家在掌握原则之后，在实际应用中不断熟练和提高。日语的敬语分成：敬他语、自谦语和郑重语3种，这里分别讲述。一、敬他语这是为了尊敬对方或者话题人物而使用的描述对方或者话题人物的行为的语言。共有如下5种形式。 1，敬语助动词----れる、られる动词未然形(五段动词)+れる动词未然形(其他动词)+られる *「先生は明日学校に来られます。」“老师明天来学校。” *「社長はこの資料をもう読まれました。」“总经理已经读过了这个资料。” 这类句子的特点是：句子结构与普通的句子相同，只是动词变成了敬语形式(未然形后面加了敬语助动词)，另外句子中的主语是一个令人尊敬的人物。另外要注意：サ变动词未然形+られる时：サ变动词词干+し(未然形)＋られる＝サ变动词词干＋される(しら约音=さ) 所以サ变动词的敬语态是：サ变动词词干+される如：「社長は会議に出席されません。」“总经理不参加会议。” 在遇到“实义动词＋て＋补助动词”加敬语助动词时，敬语助动词加到补助动词上而不加到实义动词上。如：「先生が新聞を読んでいます」改成敬语时： *「先生が新聞を読んでおられます。」(正确)(いる后面加敬语助动词时，用おる变化，成为おられる) *「先生が新聞を読まれています。」(错误) 2，敬语句形敬语句形是用固定的句形表示的敬他语。 ①お＋五段动词或一段动词连用形＋になる

ご(御)＋さ变动词词干＋になる如：「先生はもうお帰りになりますか。」“老师您要回去了吗？” 「先生は何時ごろ御出勤になりますか。」“老师您几点上班？” 这里要注意： A，当动词的连用形只有一个字母(兼用一段动词)时，不用这个句形。 B，动词是敬语动词时，不用这个句形。 c，外来语构成的动词，不用这个句形。 ②お＋五段动词或一段动词连用形＋ですご(御)＋さ变动词词干＋です如：「先生はもうお帰りですか。」“老师您要回去了吗？” 「先生は何時ごろ御出勤ですか。」“老师您几点上班？” 这里注意： A，这个句形没有时态变化，时态用相关的副词表示。如：(将来时)「先生は明日お帰りですか。」“老师明天回去吗？” (现在时)「先生は今お帰りですか。」“老师现在回去吗？” (过去时)「先生はもうお帰りですか。」“老师已经回去了吗？” B，“存じる”是“知る”的自谦语，但是可用这个句形，表示尊敬。如：「先生ご存知ですか。」“老师，您知道吗？” ③お＋五段动词或一段动词连用形＋くださるご(御)＋さ变动词词干＋くださる这个形式用在对方或话题人物对说话人有影响或受益时使用。另外，くださる后面加ます时，变成くださいます。如：「山下先生が文法をお教えくださいます。」“山下老师教我们文法。” 「いろいろご指導くださって、ありがとうございます。」“承蒙各方面指导，深感谢意。” ④お＋五段动词或一段动词连用形＋くださいご(御)＋さ变动词词干＋ください这个句形比动词连用形(五段动词音变浊化)＋て＋ください要客气。如：「先生、このお手紙をお読みください。」“老师，请读这封信。”

公司内部敬语的使用方法

首先，先发点废话。。。嘿嘿。。。以前读书的时候没觉得敬语有多重要，所以学习起来也就没那么上心。现在上班了，在日企这种环境中，不会说敬语真的是件很痛苦的事。有的时候问上司:我的说法你理解了吗? 常常会因为说法不当而憋在嘴里，怎么也开不了口。所以下定决心好好学习，天天向上~~吼吼~~ = = 废话到此为此，正题见标题，内容如下： 1、部長，私の説明がわかりますか。（误）部長，私の説明がご理解いただけたでしょうか。（正）使用上面的错误说法，会使局外人觉得：问题大概过难了吧！部长真笨，理解不了。年轻的职员如果在给部长的报告前面加上「おわかりになりますか」这样的话，部长会因此而恼怒。这是因为「わかる」这个词含有能力欠佳的意思。就是说「わかりますか」这句话是问对方有没有这个理解能力。并且，用在这里往往被认为这是在影射部长的能力低下。在这种情况下，通常要说「これでよろしいでしょうか」（这样，行不行？）或「部長，ご理解いただけたでしょうか」（部长，您理解了吧）。当然，在日常会话中可以用，但要分具体场吅。「わかる」「できる」等都是表现“能力”与“可能”的词，对上级、老师、长辈等不宜使用。但目前在这方面不主意的人却很多。应该记住：对上级、老师、尊长等，要避免使用「わかる」「できる」这些词，否则会有目无尊长之嫌。 2、課長が「おまえから伝えよ」とおっしゃいました。（误）課長が「わたしからお伝えするように」とおっしゃいました。（正）受科长之命，科员去向部长汇报时，有时会说出上面错误例句中的话。意思是，“科长说由我来汇报（所以我来了）”。部长若听到这样的话语，恐怕会感到不高兴。因为，这样的说法太直接了，也太生硬了。对于听话一方来说，「おまえ」「せよ」这类生硬的说法，是难以令人接受的粗鲁语言。这种直接引用原话的表达方式，往往容易招至误解。因此，要特别注意，以免引起听话一方的不快。碰上科员真被上司说成「君から」这样的事，通常不宜直接引用，因为「君から」用于指自己时，是不妥的，会引人发笑。谦逊地说成「おまえから」又有被误解的可能。用「わたしからお伝え申し上げるように」这样的说法最为吅适，既能间接表达语意，也不会引起

敬语

~~敬語よく使われる言い換え型の例~~

一、尊敬语（尊敬語） 1、动词的れる、られる形 a、先生は明日学校に来られます。 b、社長はこの資料をもう読まれました。 2、句型：お＋动词连用形＋になる a、先生はもうお帰りになりましたか。 3、句型：お/ご＋动词词干＋です a、先生はもうお帰りですか。 b、先生ご存知ですか。 4、お/ご＋动词连用形＋くださる a、山田先生が文法をお教えくださいます。 b、先生、この手紙をお読みください。

5、动词的敬语形（特殊）动词基本型敬语形行くいらっしゃいます来るいらっしゃいますいるいらっしゃいますするなさいます言うおっしゃいます見るご覧になる食べる召し上がる飲む召し上がる二、自谦语（謙讓語） 1、お/ご＋动词连用形＋する a、ここでお別れします。 b、では、ご案内しましょう。 2、お/ご＋动词连用形＋いたす a、先生のお荷物、私がお持ちいたします。 3、动词使役态：せていただく或せてください

a、こちらから説明させていただきます。 b、私にも行かせてください。 4、动词的自谦动词（特殊）动词基本型动词谦语型行く参ります来る参ります食べるいただきます飲むいただくますいるおります訪問する伺います言う申します見る拝見する三、郑重语（丁寧語）这一类敬语不是对话题人物的尊敬，也不是对自己的自谦，而是用郑重地说话来表示对听话人的尊重，也表示自己有高雅的教养。最基本得表现就是：です、ます其它还有：ござる、まいる、いたす、おる a、雪が降ってまいりました。

b、なにか変な匂いがいたしますよ。 c、用意ができております。大家知道敬语是日语学习中的重点难点，能在不同的场合说好敬语是非常重要的哟！据说现在连日本的年轻人都不能好好地运用敬语，那么你呢？今天我们来认识一下日语敬语体系的“基盤（きばん）”“あげる、くれる、もらう”三个词的敬语形式“差し上げる、くださる、いただく”的用法。一起攻克敬语这座大山吧！ 1、くださる（くれる）くださる和くれる意义相同，但是敬意更高，对于长辈或者有威望的人生一定要用“くださる”，会让对方觉得得到尊重。其命令形是：“ください”不过同学们注意了，虽然“……てください”也算是敬语形式，但是却有一种命令的口气，对长辈要慎用哦。例：この車は、隣のお医者さんがお譲りくださいました。/这辆汽车是我和我家住邻居的一个医生转卖给我的。先生、この文を翻訳してください。/老师，帮我翻译这篇文章。（欠妥） 2、いただく（貰う）いただく可以说是最常用的敬语之一，日本人吃饭之前的那句“いただきます”想必大家都知道吧，“いただきます”就是“いただく”的ます形。根据作用对象的不同，“いただく”可以分为两种形式哦。

敬语用法注意点

敬语用法注意点 1、2、3级试题当中可以说“一定”会有关于敬语使用的题目，很多同学反映总是很模糊、概念不清楚，看着四个选项举棋不定。有些老师的观点是，敬语所占分数有限，一般6-10分，如果实在搞不清楚的话，放弃也罢，用不着那么在意。但是我觉得，既然明白地知道试卷会考，那为什么不花点时间弄清楚呢？所以，今天说说敬语。敬语分三种：尊敬语（尊敬語）、谦逊语（謙譲語）、礼貌语（丁寧語）敬语最主要是在动词上面做文章，产生变化，以表现出对对方的尊敬、抬高对方。所以，我们先说说动词的尊敬和动词的自谦。一、动词的尊敬首先，要明确什么场合需要尊敬。先想明白“动作是谁做的？动作的主体是哪个人？”，也就是这个动作的主语、句子的主语到底是谁。如果这个人是“您”或者是“社长”“部长”等地位比自己高、需要表达尊敬的人的话，则使用尊敬语。（注意：如果是对外部的人说自己的社长、部长的话，应该“内外有别、一致对外”，不能使用尊敬语，而应该使用谦逊语，表示对外部的陌生人的尊敬）然后我们看看如果表达尊敬，有3种方法。 1、动词变为被动形式，可以表示尊敬。这种形式表达的尊敬程度最低，一般公司内部的男性对上级使用，语气较为生硬。社長は10時に来られます。社长先生10点钟来。お酒をやめられたんですか。您戒酒了么？ 2、お～～になる中间连接：五段、一段动词（即1、2类动词）的连用形（即ます形）。

这种形式表达的尊敬程度较高，一般都可以使用，但是这种形式变化也有它的禁忌： a、连用形变形后成为1个音节、也就是发音只有1拍的词语，不使用此方法。如：見ますーみ、寝ますーね b、サ变动词、カ变动词（即第三类动词）不使用此方法。 3、特殊的尊敬动词，有一些动词有固定的尊敬动词，记牢就好。这种形式表达的尊敬程度最高，只要有对应的尊敬动词，就应该尽量使用，少用前面2种方法。对应尊敬动词列举如下：其中，个别词语ます形变化特殊：いらっしゃる－いらっしゃいます、おっしゃるーおっしゃいます、なさるーなさいます、くださるーくださいます二、动词的自谦同样，首先要明确什么场合需要谦逊。“动作是谁做的？动作的主体是哪个人？”，这个动作的主语、句子的主语是谁。如果这个人是“我”或者是“我家、我一方的人”面对地位比自己高的人讲自己的动作，则动词使用谦逊语。谦逊语是利用“谦虚自己”的形式来达到“抬高对方”的效果，所以“内外有别、一致对外”，向外部的人讲述自己或自己内部的人的动作时，无论自己内部的人是“部长”还是“社长”，都应该使用谦逊语。然后我们看看如果表达自谦，有2种方法。1、お～（五段、一段ます形）するご～（サ变动词词干）する这种形式变化

探讨日本超市员工敬语的使用实况与技巧

Modern Linguistics 现代语言学, 2018, 6(3), 408-414 Published Online August 2018 in Hans. https://www.wendangku.net/doc/7c14589949.html,/journal/ml https://https://www.wendangku.net/doc/7c14589949.html,/10.12677/ml.2018.63045 A Study on the Application and Skills of Honorifics of Japanese Supermarket Staff Yan Liu, Xiaomei Wang* College of Foreign Languages, Guizhou University, Guiyang Guizhou Received: Jul. 9th, 2018; accepted: Jul. 21st, 2018; published: Jul. 31st, 2018 Abstract The practical application of Japanese honorifics becomes a challenge for Japanese learners. In re-cent years, many scholars have researched on the system of Japanese honorifics, teaching methods of Japanese honorific language, and the perspective of cross-cultural communication. However, there are few researches used to clarify the application of Japanese honorifics. This study aims at promoting the acquisition and application of Japanese honorifics of Japanese learners, especially of international Japanese learners studying in Japan. Keywords Supermarket Service, Japanese Honorifics, Application and Skills 探讨日本超市员工敬语的使用实况与技巧刘岩，王晓梅* 贵州大学外国语学院，贵州贵阳收稿日期：2018年7月9日；录用日期：2018年7月21日；发布日期：2018年7月31日摘要日语敬语的实际应用是日语学习者的一个困难点。近年来，很多学者围绕着日语敬语的体系，日语敬语教学方法，跨文化交际视角进行了研究，但是通过实例阐明日语敬语的使用的研究却很少。本研究以日本超市为例，探讨了超市员工的日语敬语的使用实况与技巧。希望能对日语学习者提升日语敬语的学习与使用有所帮助，尤其是对赴日留学的日语学习者有所助益。 *通讯作者。

敬语的表达

尊敬语的用法 [动词] 与えるくださるたまわる言うおっしゃる行くいらっしゃるいるあるいらっしゃるおいでになる着る召す（めす）お召しになる来るいらっしゃるみえるおいでになるおこしになるするなさるあそばす寝るお寝み（やすみ）になる食べる召し上がる见る御覧になるお目にとめるお目にとまる闻くお耳にはいる命ずるおおせつける [接头词] おごおんみおみ例如：お志ご出発 [接尾词] 様さん殿君 [代词] あなたそちら自谦语是一种降低讲话人（或讲话方面的人）的动作、所有物（所属），以此来抬高对方的一种表现。自谦语是通过自我谦虚来抬高对方的语言。例如： “私どもの方から参ります。” （这是降低讲话人的动作“行く／去”的表现。）（“还是我们到您那儿去。”） “お支度がよければこの斎藤がご案内いたします。” （这是降低讲话人的动作“案内する／带路”的表现。）（“如果您准备好了，就由齐藤我来领你们去。”） “わたしが责任をもって明日お届けいたします。” （这是一种降低了讲话人的动作的表现，结果抬高了对方身份。）（我明天负责送去。） “その件では徳中が寺上さんにご连络いたすことになっております。” （这是关于话题者之间的谈话，讲话人对对方表示了自我谦虚。）（“关于那件事，决定由德中同寺上先生联系。”）很多人经常犯的一个错误就是：当自己是主动者时，虽然也想用自谦语来表达自己的意思，但当需要讲自己这方面的事情转告对方时，就经常忘了要使用自谦语。自谦语不仅用于自己或自己的行为，而且当自己向对方（第三者）谈到自己方面的事情

时，即使所谈的人是你尊敬的长辈或上司，仍然必须使用降低己方的表达方法。尊敬语固然重要，但自谦语也必须习惯使用。自谦语的用法 [动词] 会うお目にかかる言う申し上げる申す行く参るうかがう借りる拝借（はいしゃく）する闻かせるお耳に入れる闻く承る（うけたまわる）拝聴（はいちょう）するうかがう知る存ずる存じ上げる承知する来る参る质问するうかがうおたずねするするいたす食べる顶戴するいただく访问するうかがうあがるお邪魔する见せる御覧にいれるお目にかける见る拝见する [接头词] “小”“愚”“弊” 例如：“"小生（しょうせい）”“愚兄（ぐけい）”“弊社（へいしゃ）” [接尾词]：“ども”“ら”“など” 例如：“"私ども”“私など” 如下表所示的敬语用法正在被越来越多的人使用。尊敬语自谦语 ——れる（书かれる）——られる（来られる）お（ご）——なる（お书きになる，ご卒业になる）お（ご）——する（お待ちする，ご招待する）お（ご）——いたす（ご案内いたします，お持ちいたします）注意：在应该使用尊敬语时却错用了自谦语，即把应该用于自己或自己动作的词错用于对方身上，这是很不礼貌的说法，必须尽量避免。还要注意：即使在词的前面加上了“お（ご）”，但如果不注意后面的词尾，也会变成有失礼貌的说法。如对对方说“お持ちしない”（正确的用法应为“お持ちにならない”）、或“お待ちしてください”（正确的用法应为“お待ちになってください”）、或“（记念品を）いただいてください”（正确的用法应为“（记念品を）お受け取りになってください”）等，这样的说法都是不对的。如果觉得“お——なる”这种模式不顺口，也可以省去“なる”，说成诸如“お待ちください”以及“お受け取りください”等，也是可以的。而且要知道，要表示敬意，也不是非要拘泥于这种尊敬语及自谦语模式的表达方式不可。

谦辞、敬语的用法

语言表达的得体高考常考敬词、谦词、雅语汇总语言表达的得体是指能够恰当地使用语言，体现语境和语体的要求。“得体”就是根据语境条件使用语言，即根据内部语境(上下文文体、句式、语言间的搭配和使用习惯等)和外部语境(语言交际的各种情境条件，如说话的目的、场合，需要表达的方式，发话者的身份、职业、处境，受话者的年龄、经历、思想性格、心理需求等)，选用恰当的语句来表情达意，这是比“简明、连贯”更高一层的要求。 1、要考虑对象，即根据不同交际对象的社会背景、文化修养、语言习惯等采用相应的语言形式。 2、要考虑场合，在不同场合(如正式场合、工作场合、日常生活、娱乐场所等)采用不同的语言形式。 3、要考虑目的，目的不同，语言表达自然有别。如广播稿是念给人听的，所以要多用短句、口语，不容易引起歧义的词和生僻的词等。再如失物招领启事语言要简洁，寻物启事语言要较详细等。 4、要考虑表达方式，表达方式的差异主要指不同语体所用的表达方式不同。语体分谈话语体和书面语体两大类。谈话语体包括日常谈话、演讲、辩论等;书面语体分为文学语体、政论语体、科学语体、事务语体等。敬词 1.“拜”字族拜读：读对方作品。拜会：和对方见面。拜望：看望或探望对方。拜托：请对方帮忙。2.“奉”字族奉告：告诉对方。奉还：对方的物品归还。奉送：赠送对方礼物。 3.“高”字族高就：询问对方在哪里工作。高龄、高寿：指老人家年龄。高见：指对方的见解。高攀：和他人交朋友或结成亲戚。高堂：称对方父母。高足：称对方的学生或徒弟。 4.“贵”字族贵姓：询问对方的姓。贵庚：询问对方的年龄。贵恙：称对方的病。 5.“惠”字族

惠赠：指对方赠予(财物)。惠存：多用于送对方相片、书籍等纪念品。惠顾：商家称顾客到来。惠临：指对方到自己这里来。惠允：指对方允许自己做某事。 6.“令”字族令堂：尊称对方的母亲。令尊：尊称对方的父亲。令媛：尊称对方女儿。令爱：尊称对方女儿。令郎：尊称对方的儿子。 7.“宝”字族宝号：称对方的店铺。宝眷：称对方的家眷。 8.“呈”字族呈正：指把自己的作品送交别人批评指正。呈报：指用公文向上级报告。呈请：指用公文向上级请示。 9.“垂”字族垂问：表示别人(多指长辈或上级)对自己的询问。垂爱：称对方(多指长辈或上级)对自己的爱护(多用于书信)。垂询：称对方(多指顾客)对本企业事务的询问。 10.“光”字族光临：称对方到来。光顾：商家多用以欢迎顾客。 11.其他敬词壁还：用于归还对方物品。俯就：请对方同意担任某一职务。斧正：请对方修改文章。恭候：用于等待对方。借问：用于向别人打听事情。千金：称别人的女儿雅正：把自己的书画等送人时表示请对方指教。鼎力：用于向对方表示感谢。华诞：称对方的生日。谦词中生学习”微信号（ID 1.“家”字族用于对别人称比自己辈分高或年纪大的亲属。家父、家严：称自己的父亲。家慈：称自己的母亲。家兄：称自己的兄长。“高中生

社内敬语的使用方法(1)

社内敬语的使用方法(1) 1、部長，私の説明がわかりますか（误）部長，私の説明がご理解いただけたでしょうか（正）使用上面的错误说法，会使局外人觉得：问题大概过难了吧！部长真笨，理解不了。年轻的职员如果在给部长的报告前面加上「おわかりになりますか」这样的话，部长会因此而恼怒。这是因为「わかる」这个词含有能力欠佳的意思。就是说「わかりますか」这句话是问对方有没有这个理解能力。并且，用在这里往往被认为这是在影射部长的能力低下。在这种情况下，通常要说「これでよろしいでしょうか」（这样，行不行？）或部長，ご理解いただけたでしょうか」（部长，您理解了吧）当然，在日常会话中可以用，但要分具体场合。「わかる」「できる」等都是表现“能力”与“可能”的词，对上级、老师、长辈等不宜使用。但目前在这方面不主意的人却很多。应该记住：对上级、老师、尊长等，要避免使用「わかる」、「できる」这些词，否则会有目无尊长之嫌。 2、課長が「おまえから伝えよ」とおっしゃいました（误）課長が「わたしからお伝えするように」とおっしゃいました（正） “科长说由我受科长之命,科员去向部长汇报时.有时会说出上面错误例句中的话意思是，来汇报（所以我来了）”。部长若听到这样的话语，恐怕会感到不高兴.因为,这样的说法太直接了,也太生硬了。对于听话一方来说，「おまえ」「せよ」这类生硬的说法，是难以令人接受的粗鲁语言。

这种直接引用原话的表达方式,往往容易招至误解.因此,要特别注意以免引起听话一方的不快。碰上科员真被上司说成「君から」这样的事，通常不宜直接引用，因为「君から」用于指自己时，是不妥的，会引人发笑。谦逊地说成「おまえから」又有被误解的可能。用「わたしからお伝え申し上げるように」这样的说法最为合适，既能间接表达语意，也不会引起误解，对于类似部长的上司又不失礼。 3 部長,それでは,お教えします.（误）部長,それでは,ご説明いたします（正）如果部长对一个下属说：「ここがちょっとわからないので、教えてくれないか」，而下属则回答说：「はい、それではお教え申し上げます」。这样的回答是不妥的。部长听了一定会生气的。因为对上司，用「教える」这样的词语，会给听者一种“看不起自己”的感觉。即使用「お教え申しあげます」这一更自谦的说法，也是一样因为「教える」这个词含有自上而下“教”的这层意思，因此会令听者感到不高兴。这里应该用「ご説明（いた）します」为宜。 4 社長は.ゴルフをおやりになりますか（误）社長は，ゴルフをなさいますか（正）不少人常常使用「おやりになる」这句别扭的敬语。「社長は，奥様とゴルフをおやりになりますか。」

不同场合的各种自我介绍(完整版)

不同场合的各种自我介绍不同场合的各种自我介绍第一篇：不同场合的各种自我介绍以下就分享一篇不同场合所使用不一样的自我介绍，供各位准备去求职的大学生参考一下。许多招聘者都说，见到应聘者的第一眼，他们就开始决定是否聘用他，等到应聘者作完自我介绍，结论已经基本定下。这就是众所周知的前因效应。对于你面前的人来说，你的脸就是你的名片，而你的自我介绍就是名片的注解。给人留下深刻印象是必要的，更重要的是这印象应该是良好的，能激发对方对你深入了解的愿望。一段精心设计的自我介绍就是一个商业广告，一个产品包装，成功与否就在于你能否灵活变化，在任何环境中都把最适合的一面充分展现出来。人是同一个人，不同场合中，自我介绍的方式和内容不能一成不变。不一样的场合，如何让别人认识你自我介绍，无非就是告诉别人你是谁，你是一个什么样的人。作自我介绍的方法多种多样，应随时随地而变。自我介绍可分为主动和被动两大类型。主动自我介绍适用于想结识某人而又无人引见的情况，被动自我介绍适用于别人想了解自己，主动前来询问的情况。在一些公共场合和一般性社交场合，如社区舞会、旅途中、普通的电话沟通等，彼此没有深入交往的意向，可以使用应酬式自我介绍，简单告诉对方你的名字即可。

在工作场合，如接待客户、接待上级领导、参加业内人士聚会等，需要用到工作式自我介绍，内容应包括自己完整的姓名、所在单位及部门、职务或工作性质等详细个人信息。除非从事保密工作，自我介绍时应尽量使用以上3项内容全面准确。比如我们可以说：你好，我是某单位某部门的经理助理，主要负责行政工作。在有意与某人深交的社交场合中，我们可以用社交式自我介绍。具体内容应包括你的姓名、职业、籍贯、兴趣爱好等，可多说一些能使人对你加深印象的内容。如果你认识对方的熟人，你可以告诉对方：我听某某说起过你、我和您的朋友某某是校友。如果你的姓名用字不容易让人明白，你要适时说明。例如你叫程隆，你要告诉对方：程，前程的程，隆，兴隆的隆，可不是明星成龙的那两个字哦！在报告、庆典、仪式、演出等正式场合，可以用礼仪式自我介绍。具体内容应包括自己的姓名、单位、职务，如果是参加演讲比赛，自我介绍还应包括自己的参赛编号。在应聘、公务、商务交往等场合，当别人主动询问你的个人情况时，就要用到问答式自我介绍了。对方可能会问：简单介绍一下你自己好吗？请问您贵姓？您哪里高就？我们根据对方的问题逐一回答即可。正式场合的自我介绍，一定要使用谦词和敬语。谦语和敬语体现了说话者的修养。它们是同一事物的两个方面，即对人使用敬语时，对己则使用谦语。常见的谦语有错爱、斗

相关文档

敬语具体的使用场合

相关文档

各种场合使用的敬语集锦

何时用敬语办公室谈吐礼仪

敬语具体的使用场合

敬语用法注意点

商务日语中敬语的使用规则研究

敬语用法

交谈常用敬语

敬语服务

敬语的表达

敬语

各种场合使用的日语敬语集锦

敬语的运用场合及基本用语

敬语

不同场合的各种自我介绍(完整版)

尊敬语的用法

发邮件或者正式场合会用到的敬语

敬语用法归纳总结

探讨日本超市员工敬语的使用实况与技巧

敬语谦语雅语

敬语

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)

Connected K-target coverage problem in wireless sensor networks with different observation scenarios

敬语

敬语

各种场合使用的日语敬语集锦

何时用敬语 办公室谈吐礼仪

敬语使用

敬语具体的使用场合

敬语用法归纳总结

公司内部敬语的使用方法

敬语

敬语用法注意点

探讨日本超市员工敬语的使用实况与技巧

敬语的表达

谦辞、敬语的用法

社内敬语的使用方法(1)

不同场合的各种自我介绍(完整版)

何时用敬语办公室谈吐礼仪